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]; } }

YMSF

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