Minimum Path Sum

Q:
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.

A:
就是简单的DP 问题。 从bottom-right 开始，计算，到top-left截止。

public class Solution {
    public int minPathSum(int[][] grid) {
        // as we do not need to print the path, 
        // we only record their minimum sum
        // DP method, calcuated from bottom-right to up-left
        int m = grid.length;
        int n = grid[0].length;
        int[][] minSum = new int[m][n];
        minSum[m-1][n-1] = grid[m-1][n-1];
        
        // calculate bottom row
        for (int j = n-2; j >=0 ; j--) {
            minSum[m - 1][j] = grid[m - 1][j] + minSum[m - 1][j+1];
        }
        // copy most right row
        for (int i = m-2; i >= 0 ; i--) {
            minSum[i][n - 1] = grid[i][n - 1] + minSum[i+1][n-1];
        }
        // calculate backward.
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                minSum[i][j] = grid[i][j]
                        +  Math.min(minSum[i + 1][j], minSum[i][j + 1]);
            }
        }
        return minSum[0][0];
    }
}

Mistakes:
1: 计算最下面一行和最右边一列的时候，不是简单的copy而应该是到右下角点的sum的值。


----------------------------------------------第二遍------------------------------------
思路：刚开始扫描第一行和第一列
然后，每次再扫描并计算 剩下的grid的第一行和第一列。 分别update 节点的值。

public class Solution {
    // work directly on the same list 
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int i =0;i< m;i++){
            for(int j =0;j< n;j++){
                if(i==0){
                    grid[i][j] += j==0?0:grid[i][j-1];
                }else if( j==0 ){
                    grid[i][j] += grid[i-1][j];
                }else{
                    grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
                }
            }
        }
        return grid[m-1][n-1];
    }
} 

Mistakes：