Leetcode 64 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.

思路：典型dp。每一步的最小路径值等于当前方格数值加上前面两个两个方向（左和上）中较小路径值。

　　　边界条件为第一行和第一列，第一行的只用考虑左方向，第一列只用考虑上方向。

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