最小路径和

[JesseZhao1990]

function minPathSum(grid){
    if(!grid || grid.length===0) return 0;
    var m = grid.length;
    var n = grid[0].length;
    var dp = new Array(n);
    dp[0] = grid[0][0];

    for(var j=1;j<n;j++){
        dp[j] = dp[j-1] + grid[0][j];
    }

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

    return dp[n-1];
}

解题思路：

由于到达某个点的路径只能是从左侧或者是上侧因此，到达第一个点0,0的最小路径，就是grid[0,0],
我们记为dd[0,0]。到达01的最小路径为到达0,0的最小路径加上grid[0,1],我们记为dd[0,1]。

以此类推，我们可以算出到达第一行的任意一个点的最小路径，我们再来看第二行，第二行的第一个点1,0
到达此点的最小路径为从头部过来，也就是dd[0,0]+grid[1,0]，我们记为dd[1,0]。然后我们再看第二行的第二个点，1,1 。这个点为最小路径为min(dd[1,0],dd[0,1])+grid[1,1]，我们记为dd[1,1]。

以此类推，一行行的算出来到达每个点的小路径。一直算到最后一行的最后一个，此时得出结论

上边的代码是这种思路的精简版。没有采用二维数组记忆。而是采用了一位数组记忆。更节约空间。

LeetCode原题地址：https://leetcode-cn.com/problems/minimum-path-sum/description/