二维数组的最小路径和问题

朴灿烈づ我的快乐病毒、 2024-04-06 11:21 35阅读 0赞

> 给定一个只含非负整数的`m ∗ n`网格，找到一条从左上角到右下角的可以使数字和最小的路径。

### 暴力解法（超时）[\#][Link 1] ###

定义递归函数

int process(int[][] grid, int i, int j)

递归含义：从`i,j`开始，一直到最后，最小的路径和是多少。

主方法直接调用

// 从0，0开始，一直到最后，最小路径和是多少
    process(grid,0,0)

即为答案。

base case 为:

1.  当前点已经到最后一行了,只能向右走。
2.  当前点已经到最后一列了,只能向下走。

如下代码:

// 到最后一行了，只能向右走
            if (i == grid.length - 1) {
                int sum = 0;
                for (int m = j; m < grid[0].length; m++) {
                    sum += grid[i][m];
                }
                return sum;
            }
            
            // 到最后一列了，只能向下走
            if (j == grid[0].length - 1) {
                int sum = 0;
                for (int m = i; m < grid.length; m++) {
                    sum += grid[m][j];
                }
                return sum;
            }

针对普遍位置,即可以向下走,也可以向右走,决策出最小路径即可。

// 普遍位置
            int p1 = grid[i][j], p2 = grid[i][j];
            if (i + 1 < grid.length) {
                // 向下走
                p1 += process(grid, i + 1, j);
            }
            if (j + 1 < grid[0].length) {
                // 向右走
                p2 += process(grid, i, j + 1);
            }
            return Math.min(p1, p2);

暴力解法完整代码如下

// 暴力解，超时
        publ

[Link 1]: https://www.cnblogs.com/greyzeng/p/16712777.html#%E6%9A%B4%E5%8A%9B%E8%A7%A3%E6%B3%95%E8%B6%85%E6%97%B6