动态规划路径问题

leetbook: https://leetcode.cn/leetbook/detail/path-problems-in-dynamic-programming/

题目	难度
62. 不同路径	中等
63. 不同路径 II	中等
64. 最小路径和	中等
120. 三角形最小路径和	中等
931. 下降路径最小和	中等
1289. 下降路径最小和 II	困难
1575. 统计所有可行路径	困难
576. 出界的路径数	中等
1301. 最大得分的路径数目	困难	TODO
剑指 Offer 47. 礼物的最大价值	中等	同 64

62. 不同路径

public class Solution62 {
    public int uniquePaths(int m, int n) {
        // f[i][j] 表示到达坐标 (i,j) 的不同路径数
        int[][] f = new int[m][n];
        // 初始状态
        f[0][0] = 1;
        for (int i = 1; i < m; i++) {
            f[i][0] = 1;
        }
        for (int j = 1; j < n; j++) {
            f[0][j] = 1;
        }
        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i][j - 1] + f[i - 1][j];
            }
        }
        return f[m - 1][n - 1];
    }
}

63. 不同路径 II

public class Solution63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // f[i][j] 表示到达坐标 (i,j) 的路径总数
        int[][] f = new int[m][n];
        // 初始状态
        f[0][0] = 1;
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 0) {
                f[i][0] = 1;
            } else {
                break;
            }
        }
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 0) {
                f[0][j] = 1;
            } else {
                break;
            }
        }
        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    f[i][j] = f[i][j - 1] + f[i - 1][j];
                } else {
                    // 不可达
                    f[i][j] = 0;
                }
            }
        }
        return f[m - 1][n - 1];
    }
}

64. 最小路径和

public class Solution64 {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // f[i][j] 表示到达 grid[i][j] 矩阵的最小路径和
        int[][] f = new int[m][n];

        // 初始状态 第一行 + 第一列
        f[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            f[0][j] = f[0][j - 1] + grid[0][j];
        }

        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
}

120. 三角形最小路径和

import java.util.List;

public class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 三角形的高度
        int h = triangle.size();
        // f[i][j] 为自底向上到 [i,j] 的最小路径和。+1 避免最后一层越界
        int[][] f = new int[h + 1][h + 1];
        // 状态转移
        for (int i = h - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return f[0][0];
    }
}

931. 下降路径最小和

import java.util.Arrays;

public class Solution931 {
    public int minFallingPathSum(int[][] matrix) {
        // n x n 的 方形 整数数组
        int n = matrix.length;

        // f[i][j] 表示到 matrix[i][j] 的下降路径最小和
        int[][] f = new int[n][n];
        // 初始状态
        // dp[][] 首行等于 matrix[][] 首行
        System.arraycopy(matrix[0], 0, f[0], 0, n);
        // 状态转移
        for (int i = 1; i < n; i++) {
            int[] pre = f[i - 1];
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    f[i][j] = Math.min(pre[j], pre[j + 1]);
                } else if (j < n - 1) {
                    f[i][j] = Math.min(pre[j - 1], Math.min(pre[j], pre[j + 1]));
                } else {
                    f[i][j] = Math.min(pre[j - 1], pre[j]);
                }
                f[i][j] += matrix[i][j];
            }
        }
        return Arrays.stream(f[n - 1]).min().orElseThrow();
    }
}

1289. 下降路径最小和 II

import java.util.Arrays;

public class Solution1289 {
    // 时间复杂度 O(n^3)
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;

        // f[i][j] 表示到 matrix[i][j] 的下降路径最小和
        int[][] f = new int[n][n];
        // 初始状态
        // dp[][] 首行等于 matrix[][] 首行
        System.arraycopy(grid[0], 0, f[0], 0, n);
        // 状态转移
        for (int i = 1; i < n; i++) {
            int[] pre = f[i - 1];
            for (int j = 0; j < n; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    if (k == j) {
                        continue;
                    }
                    min = Math.min(min, pre[k]);
                }
                f[i][j] += min + grid[i][j];
            }
        }
        return Arrays.stream(f[n - 1]).min().orElseThrow();
    }
}

（全文完）