Minimum Path Sum leetcode

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.

• state: f[x][y]从起点走到x,y的最短路径
• function: f[x][y] = min(f[x-1][y], f[x][y-1]) + At[x][y]
• intialize: f[0][0] = cost[0][0]
• // f[i][0] = sum(0,0 -> i,0)
• // f[0][i] = sum(0,0 -> 0,i)
• answer: f[n-1][m-1]
• 时间O(m*n) 空间O(m*n)

public class Solution {
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0 || grid == null) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int [][] sum = new int [m][n];
        sum[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            sum[i][0] = sum[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            sum[0][j] = sum[0][j-1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                sum[i][j] = Math.min(sum[i-1][j], sum[i][j-1]) + grid[i][j];
            }
        }
        return sum[m-1][n-1];
    }
}