Java 中的矩阵最大和路径问题

这是顶级 IT 公司（如 **Google、Amazon、TCS、Accenture** 等）面试中经常遇到的问题。通过解决这个问题，可以考察应聘者的逻辑思维能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑来解决 **矩阵最大路径和问题**。我们还将为此创建 Java 程序。

问题陈述

给定一个 n×m 的矩阵。在这个矩阵中，我们必须找到最大路径和。从左上角到右下角的移动是允许的。移动方向必须是向右、向下或向右对角线（从 (i, j) 到 (i+1, j)、(i, j+1) 或 (i+1, j+1)）。

问题解决方案

要找到最大路径和，我们必须找到矩阵第一行的最大值。将此值存储在 res 变量中。现在，对于矩阵中的每个元素，更新该元素为可以包含在 **最大路径** 中的最大值。如果该值大于 res 变量，则更新 res 变量。最后返回包含 **最大路径和值** 的 res 变量。

让我们通过一个例子来理解。

矩阵最大路径和示例

输入矩阵

输出

 
500   

解释

示例 2

输入矩阵

输出

 
3000   

解释

示例 3

输入矩阵

输出

 
2300   

解释

我们可以通过以下三种方法解决上述问题。

• 使用递归
• 使用动态规划
• 使用制表法

方法：使用递归

矩阵最大路径和问题的朴素递归方法涉及递归地探索从矩阵顶部到底部的所有可能路径，计算最大和路径，而不利用记忆化来存储计算结果。

算法

步骤 1： 定义一个具有 main 方法的 MatrixMaxSumPathNaive 类，用于初始化一个示例整数矩阵。

步骤 2： 创建一个 maxSumPath 方法，该方法接受一个二维整数数组 matrix 作为输入。确定矩阵的行数 rows 和列数 cols。通过调用 maxSumPathRecursive(matrix, 0, 0, rows, cols) 开始递归。

步骤 3： 定义一个私有静态方法 maxSumPathRecursive 来递归查找最大和路径。参数包括 matrix、当前行 current row、当前列 current col、总行数 total rows 和总列数 total cols。

• 基本情况： 如果 row 等于 rows - 1，表示最底部一行，则返回 matrix[row][col]。
• 初始化： 将 maxPathSum 初始化为 Integer.MIN_VALUE。

步骤 4： 计算最大路径和，方法是：

• 向下移动：matrix[row][col] + maxSumPathRecursive(matrix, row + 1, col, rows, cols)。
• 向下左移动（如果 col > 0）：matrix[row][col] + maxSumPathRecursive(matrix, row + 1, col - 1, rows, cols)。
• 向下右移动（如果 col < cols - 1）：matrix[row][col] + maxSumPathRecursive(matrix, row + 1, col + 1, rows, cols)。

步骤 5： 返回 maxPathSum，即从当前单元格找到的最大和路径。

步骤 6： 在 main 方法中调用 maxSumPath(matrix) 后，打印结果以显示使用朴素递归方法在矩阵中找到的最大和路径。

让我们在 Java 程序中实现上述步骤。

使用递归实现矩阵最大路径和问题

文件名：MatrixMaxSumPathNaive.java

输出

 
Maximum sum path in the matrix (naive approach): 17   

时间复杂度： 朴素递归方法的时间复杂度为 O(3^n)，其中 n 是矩阵的行数。这是因为从每个单元格，函数可以移动到三个可能的方向（下、左下、右下），导致指数级的递归调用。

辅助空间： 辅助空间为 O(n)，其中 n 是行数。空间由递归堆栈使用，在最坏情况下，递归的最大深度等于行数。

方法：动态规划

动态规划是一种解决问题的技术，其中子问题的解决方案被存储和重用，以有效地解决问题的更大实例。它通过将复杂问题分解为更简单的重叠子问题来最优地解决它们，通常使用表格（记忆化）或自底向上的方法来迭代地构建解决方案。

算法

步骤 1： 定义 MAX_SIZE 来表示矩阵的最大尺寸，并声明 numRows、numCols、matrix、dp 和 visited 数组。

步骤 2： 实现 inputMatrix() 来设置 numRows、numCols，并用值填充 matrix。

步骤 3： 定义 maximumSumPath(int row, int col) 来计算从单元格 (row, col) 的最大和路径。

步骤 4： 如果位于右下角，则返回其值。如果单元格已被访问，则从 dp 返回存储的值。将其标记为已访问，并将 visited[row][col] 设置为 1。

步骤 5： 初始化 totalSum。如果不在最后一行或最后一列，则计算从向右、向右对角线或向下移动的最大和。

• 如果在最后一行，则只向右移动。
• 如果在最后一列，则只向下移动。
• 将当前单元格的值加到获得的和的最大值中。
• 用 totalSum 更新 dp[row][col]。

步骤 6： 返回当前单元格更新后的最大和值。

步骤 7： 调用 inputMatrix()。调用 maximumSumPath(0, 0) 从左上角找到最大和路径，并打印结果。

让我们在 Java 程序中实现上述步骤。

使用动态规划实现矩阵最大路径和问题

文件名：MatrixMaxSumPath.java

输出

 
Maximum sum path in the matrix: 29   

时间复杂度： 时间复杂度为 O(n×m)，因为由于记忆化，每个单元格最多只处理一次。

辅助空间： 辅助空间为 O(n×m)，用于 dp 和 visited 数组。

方法：使用制表法

在此方法中，使用动态规划 (DP) 表来迭代地计算从矩阵右下角到左上角的最大和路径。自底向上的方法通过增量构建解决方案来避免冗余计算并确保最优子结构。

算法

步骤 1： 定义一个函数 maxSumPath(int[][] matrix) 来查找给定矩阵中的最大和路径。

步骤 2： 初始化变量 rows 和 cols 来存储矩阵中的行数和列数，并创建一个大小为 rows x cols 的二维数组 dp 来存储最大和。

步骤 3： 将 dp[rows - 1][cols - 1] 设置为 matrix[rows - 1][cols - 1]，表示矩阵的右下角。

步骤 4： 遍历 dp 的最后一行和最后一列以计算最大和

• 对于最后一行（i = rows - 2 到 0）：dp[i][cols - 1] = matrix[i][cols - 1] + dp[i + 1][cols - 1]。
• 对于最后一列（j = cols - 2 到 0）：dp[rows - 1][j] = matrix[rows - 1][j] + dp[rows - 1][j + 1]。

步骤 5： 遍历 dp 表的其余部分，从右下角到左上角（i = rows - 2 到 0，j = cols - 2 到 0）

• 将每个 dp[i][j] 计算为 matrix[i][j] + max(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])，确保保持在矩阵边界内。

步骤 6： 从矩阵左上角开始的最大和路径存储在 dp[0][0] 中。

让我们在 Java 程序中实现上述步骤。

使用制表法实现矩阵最大路径和问题

文件名：MatrixMaxSumPathTabulation.java

输出

 
Maximum sum path in the matrix (tabulation approach): 35   

时间复杂度： 所提供代码的时间复杂度为 O(n×m)，其中 n 是矩阵的行数，m 是矩阵的列数。这是因为矩阵中的每个单元格都恰好处理一次。

辅助空间： 所提供代码的辅助空间为 O(n×m)，其中 n 是矩阵的行数，m 是矩阵的列数。这是因为需要为大小为 n×m 的动态规划表 (dp) 提供额外的空间。