64. 最小路径和

状态定义：dp[i][j] 表示到达 （i，j）处的最小数字总和

问题目标：dp[n][m]

状态转移：由于每次只能往右或往下移动，那么 dp[i][j] 必然与 dp[i-1][j] （注：（i-1，j）往下走一步到（i，j)) 和 dp[i][j - 1]有关，又由于题目对路径的格子加了约束（有些格子不能访问），那么有
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j]

状态初始化：dp[1][1] = 1，且 dp 中第一行、第一列为累加数组

时间复杂度：O(m * n)

空间复杂度：O(m * n) ——可优化

原始代码

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        //初始化dp
        dp[1][1] = grid[0][0];
        for(int i = 2; i <= n; i++){ //第一行
            dp[1][i] = dp[1][i-1] + grid[0][i-1];
        }
        for(int i = 2; i <= m; i++){ //第一列
            dp[i][1] = dp[i-1][1] + grid[i-1][0];
        }
        for(int i = 2; i <= m; i++){
            for(int j = 2; j <= n; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
}

如何记录最优路径？

class Solution {
    int m, n;
    public int minPathSum(int[][] grid) {        
        m = grid.length;
        n = grid[0].length;
        int[][] f = new int[m][n];
        int[] g = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[i][j] = grid[i][j];
                } else {
                    int top  = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
                    int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                    f[i][j] = Math.min(top, left);
                    g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1);
                }
            }
        }
        // 从「结尾」开始，在 g[] 数组中找「上一步」
        int idx = getIdx(m - 1, n - 1);
        // 逆序将路径点添加到 path 数组中
        int[][] path = new int[m + n][2];
        path[m + n - 1] = new int[]{m - 1, n - 1};
        for (int i = 1; i < m + n; i++) {
            path[m + n - 1 - i] = parseIdx(g[idx]);
            idx = g[idx];
        }
        // 顺序输出位置
        for (int i = 1; i < m + n; i++) {
            int x = path[i][0], y = path[i][1];
            System.out.print("(" + x + "," + y + ") ");
        }
        System.out.println(" ");
        return f[m - 1][n - 1];
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
    int getIdx(int x, int y) {
        return x * n + y;
    }
}