leetcode: Minimum Path Sum

问题描述：

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

原问题链接：https://leetcode.com/problems/minimum-path-sum/

 

问题分析

　　这个问题其实和前面分析unique path的思路基本上一致。我们要求从最左上节点到最右下节点之间的最短距离，而且每次移动只能选择向下或者向右。那么对于初始节点来说，它的最短路径就取决于它的下面那个节点和右边那个节点哪个更小。而要求出它下面的节点和右边的节点的值，则需要进一步看这两个节点的下面和右边的元素。因此，这就构成了一个递推的关系。

　　再加上前面的一个基础条件，当处在最下面一行和最右边一列的元素，它们的路径是唯一的，所以它们到终点的距离就是它当前的值和到终点元素的和。而对于其他节点的元素，它的最短路径则符合如下的规律：

　　path[i][j] = path[i][j] + Math.min(path[i + 1][j], path[i][j + 1]);

　　在具体的实现里，我们可以利用原有的矩阵，而不用去额外声明一个矩阵。这样可以偷点懒。

　　详细的实现如下：

 

public class Solution {
    public int minPathSum(int[][] grid) {
        int min = 0, m = grid.length, n = grid[0].length;
        for(int i = n - 2; i >= 0; i--) grid[m - 1][i] += grid[m - 1][i + 1];
        for(int i = m - 2; i >= 0; i--) grid[i][n - 1] += grid[i + 1][n - 1];
        for(int i = m - 2; i >= 0; i--) {
            for(int j = n - 2; j >= 0; j--) {
                grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]);
            }
        }
        return grid[0][0];
    }
}