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

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

暴力解法（超时）#

定义递归函数

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