LintCode 110. 最小路径和 JavaScript算法

描述

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

说明

你在同一时间只能向下或者向右移动一步

样例

- 样例 1:
	输入:  [[1,3,1],[1,5,1],[4,2,1]]
	输出: 7
	
	样例解释：
	路线为： 1 -> 3 -> 1 -> 1 -> 1。


- 样例 2:
	输入:  [[1,3,2]]
	输出:  6
	
	解释:  
	路线是： 1 -> 3 -> 2

解析

看题目就知道 老动态规划了

 minPathSum = function (grid) {
    row = grid.length;
    if (row < 1) return 0;
    col = grid[0].length;
        
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            if (i == 0 && j > 0) {
                grid[i][j] += grid[i][j - 1];
            } else if (i > 0 && j == 0) {
                grid[i][j] += grid[i - 1][j];
            } else if ( i > 0 && j > 0){
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][ j -1]);
            }
        }
    }
    return grid[row - 1][col - 1];
}

运行结果