Tuesday, February 3, 2015

LeetCoe [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.
Example:
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; ++i) dp[i][0] = INT_MAX;
        for(int j=0; j<=n; ++j) dp[0][j] = INT_MAX;
        
        for(int i=1; i<=m; ++i)
        {
            for(int j=1; j<=n; ++j){
                if(i==1 && j==1) dp[i][j] = grid[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
//Java
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        if(m==0) return 0;
        int n = grid[0].length;
        if(n==0) return 0;
        
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(i>0 && j>0) grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
                else if(i>0) grid[i][j] += grid[i-1][j];
                else if(j>0) grid[i][j] += grid[i][j-1];
            }
        }
        
        return grid[m-1][n-1];
    }
}

题目本身没啥好说的，就是dp解；面试官在我写的过程中问了很多细节，比如如果input不是一个二维矩阵[[1,2],[2,3,4]]这样，应该怎么办，开始没搞清他想考察什么，说那return -1？后来他解释说你这样最好用raise exception这个语句…有大神能解释下为啥这样更好嘛？
at

No comments:

Post a Comment