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,INT_MAX));dp[0][1] = dp[1][0] = 0;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];return dp[m][n];}
};

分析：

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m + 1,vector<int>(n+1,INT_MAX));dp[m][n-1] = 1;for(int i = m-1; i >= 0; i--)for(int j = n-1; j >= 0; j--){dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];dp[i][j] = max(1,dp[i][j]);}return dp[0][0];}
};