• dp[ i ] [ j ] 含义

      • 从左上角点走到( i, j )点的最短路径和

      image.png

      1. public int minPathSum(int[][] grid) {
      2.    int N = grid.length;
      3.    int M = grid[0].length;
      4.    int[][] dp = new int[N][M];
      5.    dp[0][0] = grid[0][0];
      6.    for (int j = 1; j < M; j++) {
      7.        dp[0][j] = dp[0][j - 1] + grid[0][j];
      8.    }
      9.    for (int i = 1; i < N; i++) {
      10.        dp[i][0] = dp[i - 1][0] + grid[i][0];
      11.    }
      12.    for (int i = 1; i < N; i++) {
      13.        for (int j = 1; j < M; j++) {
      14.            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
      15.        }
      16.    }
      17.    return dp[N - 1][M - 1];
      18. }
    • 可以空间压缩

    image.png
    image.png
    然后我在发现在填dp表的时候，我只需要我上一行的值即可

    因此用一个一维数组
    image.png
    image.png
    image.png
    image.png
    image.png

    //空间压缩版本
    public int minPathSum2(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        // 其实应该是一张二维表，但是用了空间压缩技巧
        int[] dp = new int[M];
        // dp数组变成，想象中二维表的第0行数据
        // m : 3 2 1 6 3 5 6 12
        dp[0] = grid[0][0];
        for (int j = 1; j < M; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        for (int i = 1; i < N; i++) {
             //dp此时是想象中二维表的第i-1行数据
            // 想更新成，想象中二维表的第i行数据
            // dp[0]
            dp[0] = dp[0] + grid[i][0];
            for (int j = 1; j < M; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
            }
        }
        return dp[M - 1];
    }
    • 总结，只要动态规划是依赖于自己的临近位置，都可以做空间压缩