走楼梯——二维带权值走楼梯（四）

LeetCode_64_MinimumPathSum

题目分析：

状态转换方程
  dp[i][j] = min(dp[i-1][j] + grid[i-1][j], dp[i][j-1] + grid[i][j-1]) 
  dp[i][j]代表“到达”第i行j列所需最小花费--不包含grid[i][j]本身的花费
递推初始项
  dp[0][i] = dp[0][i-1] + grid[0][i-1];
  dp[i][0] = dp[i-1][0] + grid[i-1][0];
递推初始项的形成 这里选择横向扫描
1.为什么是第一行第一列
  和上题一样
2.值的选取
  其实也是根据递推式推出来的
  先看行，第一行上面没有行，自然只能从自身的左方推过来。
  也就是dp[i][j] = min(dp[i-1][j] + grid[i-1][j], dp[i][j-1] + grid[i][j-1]) 这个式子中，
  去掉了上方的dp[i][j-1] + grid[i][j-1]，只剩下左方的dp[i-1][j] + grid[i-1][j]
  显然dp[0][0] = 0 java默认数组值是0 也就不用手动赋值一次了再
  同理可得第一列

解法一：循环-动态规划

public static int minPathSum_dp_loop(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int dp[][] = new int[m][n];

    for (int i = 1; i < n; ++i) dp[0][i] = dp[0][i-1] + grid[0][i-1];
    for (int i = 1; i < m; ++i) dp[i][0] = dp[i-1][0] + grid[i-1][0];

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = Math.min(dp[i-1][j] + grid[i-1][j], dp[i][j-1] + grid[i][j-1]);
        }
    }
    return dp[m-1][n-1] + grid[m-1][n-1];
}

解法二：循环-动态规划-内存优化

public static int minPathSum_dp_loop_lessMemory(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int dp[] = new int[n];

    for (int i = 1; i < n; ++i) dp[i] = dp[i-1] + grid[0][i-1];
    for (int i = 1; i < m; ++i) {
        /**
         * 单独解决dp[0]累加更新问题
         */
        dp[0] += grid[i-1][0];
        for (int j = 1; j < n; ++j) {
            dp[j] = Math.min(dp[j] + grid[i-1][j], dp[j-1] + grid[i][j-1]);
        }
    }
    return dp[n-1] + grid[m-1][n-1];
}

解法二分析

和之前一样一行一行推，但是第一列不再像上一题一样是不变的1了，所以需要每轮都更新才行。

解法三：循环-动态规划-更进一步内存优化

public static int minPathSum_dp_loop_bestMemory(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if(m > n) {
        int dp[] = new int[n];

        for (int i = 1; i < n; ++i) dp[i] = dp[i-1] + grid[0][i-1];
        for (int i = 1; i < m; ++i) {
            /**
             * 单独解决dp[0]累加更新问题
             */
            dp[0] += grid[i - 1][0];
            for (int j = 1; j < n; ++j) {
                dp[j] = Math.min(dp[j] + grid[i-1][j], dp[j-1] + grid[i][j-1]);
            }
        }
        return dp[n-1] + grid[m-1][n-1];
    }else{
        int dp[] = new int[m];

        for (int i = 1; i < m; ++i) dp[i] = dp[i-1] + grid[i-1][0];
        for (int i = 1; i < n; ++i) {
            /**
             * 单独解决dp[0]累加更新问题
             */
            dp[0] += grid[0][i-1];
            for (int j = 1; j < m; ++j) {
                dp[j] = Math.min(dp[j] + grid[j][i-1], dp[j-1] + grid[j-1][i]);
            }
        }
        return dp[m-1] + grid[m-1][n-1];
    }
}

-----------------------分鸽线-----------------------
另一种划分方式

套路熟了，开始来点变化。
状态转换方程就是你的划分问题的形式，只要满足动态规划的划分方式即可，
并非一成不变。

状态转换方程
  dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
  dp[i][j]代表“经过”(已经加上该格上的值)第i行j列所需最小花费
递推初始项
  dp[0][i] = dp[0][i-1] + grid[0][i];
  dp[i][0] = dp[i-1][0] + grid[i][0];
  仔细观察和第一种划分方式是有区别的
  第一种的初始项:
  dp[0][i] = dp[0][i-1] + grid[0][i-1];
  dp[i][0] = dp[i-1][0] + grid[i-1][0];
  同样根据方程推出，只是注意，这当前划分方式下 dp[0][0] = grid[0][0]

解法一：循环-动态规划

public static int minPathSum_dp_otherWay_loop(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int dp[][] = new int[m][n];

    dp[0][0] = grid[0][0];
    for (int i = 1; i < n; ++i) dp[0][i] = dp[0][i-1] + grid[0][i];
    for (int i = 1; i < m; ++i) dp[i][0] = dp[i-1][0] + grid[i][0];

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m-1][n-1];
}

解法二：循环-动态规划-优化内存

public static int minPathSum_dp_otherWay_loop_lessMemory(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int dp[] = new int[n];

    dp[0] = grid[0][0];
    for (int i = 1; i < n; ++i) dp[i] = grid[0][i] + dp[i-1];

    for (int i = 1; i < m; ++i) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; ++j) {
            dp[j] = grid[i][j] + Math.min(dp[j-1], dp[j]);
        }
    }
    return dp[n-1];
}

解法三：循环-动态规划-进一步优化内存

public static int minPathSum_dp_otherWay_loop_bestMemory(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if(m > n) {
        int dp[] = new int[n];

        dp[0] = grid[0][0];
        for (int i = 1; i < n; ++i) dp[i] = grid[0][i] + dp[i - 1];

        for (int i = 1; i < m; ++i) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; ++j) {
                dp[j] = grid[i][j] + Math.min(dp[j - 1], dp[j]);
            }
        }
        return dp[n - 1];
    }else{
        int dp[] = new int[m];

        dp[0] = grid[0][0];
        for (int i = 1; i < m; ++i) dp[i] = grid[i][0] + dp[i - 1];

        for (int i = 1; i < n; ++i) {
            dp[0] += grid[0][i];
            for (int j = 1; j < m; ++j) {
                dp[j] = grid[j][i] + Math.min(dp[j - 1], dp[j]);
            }
        }
        return dp[m - 1];
    }
}

总结

套路依旧，微小变化也有，最主要是明白了问题并不只有一种划分方式，
通常这种带权值的至少能分为dp过程中，包含和不包含当前位置的值两种。
是不是想起了第二题？你能试着写出第二题的另一种动态转换方程并实现吗？

相应例题的 Github