剑指 Offer II 099. 最小路径之和

题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

思路

这种肯定是通过动态规划实现的，但是我们可以通过递归到记忆化递归到动态规划的思路

实现

递归之穷举

本解法思路：从左上角开始，穷举每一个位置，找到每一个位置到1的各种可能的路径，我拿到最小的哪一个就可以啦。

private static class Solution {
    // 下 左 上 右
    private int[][] dirs = {{1, 0}, {0, 1}};
    int minPathSum = Integer.MAX_VALUE;

    public int minPathSum(int[][] grid) {
        dfs(grid, 0, 0, grid[0][0]);
        return minPathSum;
    }

    private void dfs(int[][] grid, int row, int col, int sum) {
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            minPathSum = Math.min(minPathSum, sum);
            return;
        }

        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];

            if (nextRow >= grid.length || nextCol >= grid[0].length) {
                continue;
            }
            // 减枝
            if (sum > minPathSum){
                continue;
            }
            sum += grid[nextRow][nextCol];
            dfs(grid, nextRow, nextCol, sum);
            sum -= grid[nextRow][nextCol];
        }
    }
}

但是这种方式的递归有问题，有什么为题，这种递归不是找子问题，而是一种穷举，所以如果你想用这种方式找到它的记忆化递归，好像找不到（至少我没有找到），所以我们在写这种递归的时候==要想的是怎么找子问题==

递归之最小子问题

本解法思路：对于本题， 我想找1到1的最短路径，那么我可以找1的右边：3到1的最短路径，和找1的下边：1到1的最短路径，这样我们逐渐寻找子问题，然后在回溯就可以得到最终解。

private static class Solution2 {
    // 下 左 上 右
    private final int[][] dirs = {{1, 0}, {0, 1}};
    public int minPathSum(int[][] grid) {

        return dfs(grid, 0, 0);
    }

    private int dfs(int[][] grid, int row, int col) {
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            return grid[row][col];
        }
        int minPathSum = Integer.MAX_VALUE;
        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];

            if (nextRow >= grid.length || nextCol >= grid[0].length) {
                continue;
            }
            int childMinPathSum = dfs(grid, nextRow, nextCol);
            minPathSum = Math.min(minPathSum,childMinPathSum);
        }
        return minPathSum + grid[row][col];
    }
}

递归之记忆化递归

本解法思路：记忆化递归是找到子问题的前提，所以本地的思路就是在递归之最小子问题的解法上进行

记忆化递归就是保存各个节点到右下角的最短路径记录，因为这些节点有可能重复计算

leetcode测试：针对本题，上述两种方法均不能通过测试，记忆化递归勉强可以通过测试。

private static class Solution3 {
    // 下 左 上 右
    private final int[][] dirs = {{1, 0}, {0, 1}};
    int minPathSum = Integer.MAX_VALUE;

    public int minPathSum(int[][] grid) {
        int[][] memo = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            Arrays.fill(memo[i], Integer.MAX_VALUE);
        }
        return dfs(grid, 0, 0,memo);
    }

    private int dfs(int[][] grid, int row, int col,int[][] memo) {
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            return grid[row][col];
        }
        if (memo[row][col] != Integer.MAX_VALUE) {
            return memo[row][col];
        }

        int minPathSum = Integer.MAX_VALUE;
        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];

            if (nextRow >= grid.length || nextCol >= grid[0].length) {
                continue;
            }
            int childMinPathSum = dfs(grid, nextRow, nextCol,memo);
            minPathSum = Math.min(minPathSum,childMinPathSum);
        }
        memo[row][col] = minPathSum + grid[row][col];
        return memo[row][col];
    }
}

动态规划之从终点到起始点

状态转移方程：

从右下角1开始横向向左，对于2的最小值只能是3，然后对于4的最小值只能是7

从右下角1开始竖向向上，对于1的最小值只能是2，对于1的最小值只能是3

然后对于5来讲：他的最优解要么是向下要么是向右，向下是3，向左是2，那肯定是选择向左，然后最短路径是2+5=7；

最后对于每一个点都是：在向下和向右选择一个最小值。

状态转移方程：

memo[i][j] = Math.min(memo[i + 1][j], memo[i][j + 1]) + grid[i][j];

实现：

private static class Solution4 {

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] memo = new int[m][n];
        // 初始化终点
        memo[m - 1][n - 1] = grid[m - 1][n - 1];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                // 需要体检把最后一行初始化
                if (i == m - 1 && j != n - 1) {
                    memo[i][j] = memo[i][j + 1] + grid[i][j];
                    // 把最后一列初始化
                } else if (j == n - 1 && i != m - 1) {
                    memo[i][j] = memo[i + 1][j] + grid[i][j];
                } else if (j != n - 1 && i != m - 1) {
                    memo[i][j] = Math.min(memo[i + 1][j], memo[i][j + 1]) + grid[i][j];
                }
            }
        }
        return memo[0][0];
    }

}

动态规划之从起始点到终点

动态规划的三个特质：存在重复子问题、具备最优子结构、正确的状态转移方程

到现在问题，我们的第一个问题肯定是具备了，然后最优子结构是不是也有了（第二个的思路就包含着最优子结构），最后转态转移方程，一般来说我们能写到记忆化递归一般就能够找到动态规划了，关键就是状态转移方程

状态转移方程

memo[i][j] = Math.min(memo[i-1][j], memo[i][j - 1]) + grid[i][j];

从左上角开始，先计算第一列，然后计算第二列的时候我们第二列开始的值只能从上边或者左边到达，所以第二列的值一定可以由第一列确定

private static class Solution5 {

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] memo = new int[n];
        memo[0] = grid[m - 1][n - 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j != 0) {
                    memo[j] = memo[j - 1] + grid[i][j];
                } else if (j == 0 && i != 0) {
                    memo[j] = memo[j] + grid[i][j];
                } else if (j != 0) {
                    memo[j] = Math.min(memo[j - 1], memo[j]) + grid[i][j];
                }
            }
        }

        return memo[n - 1];
    }

}