LeetCode64-最小路径和-动态规划

题目描述

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

动态规划的三步操作：

• 第一步确定数组元素的含义，因为题目求的是到达右下角目的地最小和，所以我们可以用dp[i][j]表示从坐标点(0,0)到达坐标点(i,j)路径的最小和；
• 第二步确定数组元素之间的关系，除去第一行只能向右走，第一列只能向下走，中间部分的坐标点(i,j)可以从坐标点(i-1,j)或者坐标点(i,j-1)到达，即从坐标点(i,j)的上面或者左面，我们只需要从这两条路径里选择一条最小的就是坐标点(i,j)的最小路径和，关系为：dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j],i>1,j>1;
• 第三步求数组元素的初始值，第一行只能向右走，所以dp[0][0]=grid[0][0],dp[0][i]=dp[0][i-1] +grid[0][i],i>1，第一列只能向下走，所以dp[0][0]=grid[0][0],dp[i][0]=dp[i-1][0] +grid[i][0],i>1

代码实现

public class Solution64 {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        ///dp[i][j]表示从(0,0)到(i,j)的最小和
        int[][] dp = new int[rows][cols];
        ///第一行只能向右走
        for (int i = 0; i < cols; i++) {
            if (i == 0) {
                dp[0][i] = grid[0][i];
            } else {
                dp[0][i] = dp[0][i - 1] + grid[0][i];
            }
        }
        ///第一列只能向下走
        for (int i = 0; i < rows; i++) {
            if (i == 0) {
                dp[i][0] = grid[i][0];
            } else {
                dp[i][0] = dp[i - 1][0] + grid[i][0];
            }
        }
        ///除去第一行第一列的中间部分
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                ///从上面或从左面到达，取最小的路径
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        for (int i = 0; i < rows; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[rows - 1][cols - 1];
    }

    public static void main(String[] args) {
        Solution64 solution64 = new Solution64();
        int[][] array = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(solution64.minPathSum(array));
    }
}

欢迎关注南阁公众号