首页 > 代码库 > [LeetCode]64 Minimum Path Sum

[LeetCode]64 Minimum Path Sum

https://oj.leetcode.com/problems/minimum-path-sum/

http://blog.csdn.net/linhuanmars/article/details/22257673

public class Solution {
    public int minPathSum(int[][] grid) {
        
        // Only move down or right.
        // Otherwise, -oo
        
        // Validations.
        if (grid == null)
            return -1; // Invalid input
            
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] pathsum = new int[m][n];
        for (int i = 0 ; i < m ; i ++)
        {
            for (int j = 0 ; j < n ; j ++)
            {
                int v = 0;
                if (i == 0 && j == 0)
                {
                    v = grid[i][j];
                }
                else if (i == 0)
                {
                    v = pathsum[i][j - 1] + grid[i][j];
                }
                else if (j == 0)
                {
                    v = pathsum[i - 1][j] + grid[i][j];
                }
                else
                {
                    v = Math.min(pathsum[i][j - 1], pathsum[i - 1][j]) + grid[i][j];
                }
                pathsum[i][j] = v;
            }
        }
        return pathsum[m - 1][n - 1];
    }
}


[LeetCode]64 Minimum Path Sum