https://leetcode-cn.com/problems/minimum-path-sum/

原题

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

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

思路

到每个节点的最短路径值可以通过该节点的上一个节点的最短路径和左一个节点的最短路径得到，取路径值较小的节点加上本身值即可。

• 初始化第一行dp[0][1…n]和第一列dp[1…n][0]的值，每个值等于节点本身的值加dp的前一列/前一行的值。
• dp[1][1]的最小值是dp[0][1]和dp[1][0]的值加上grid[1][1]本身的值
• dp[1][2],dp[2][1]…都能以此类推

状态转移方程：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

代码

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