leetcode 64最小路径和
2019-02-14 本文已影响0人
橘子煲汤
很简单的题目 多打了一个等号 结果找错找了半天 也是使用了dp来完成这个题目这应该算是一道用来比较好理解dp的一道题目
class Solution {
public:
int minPathSum(vector<vector<int>>& nums) {
if(nums.size()==0) return -1;
if(nums.size()==1&&nums[0].size()==1) return nums[0][0];
int row=nums.size();
int column=nums[0].size();
vector<vector<int>> dp(row, vector<int>(column, 0));
dp[0][0]=nums[0][0];
//给行赋值
for(int i=1;i<row;i++)
{
dp[i][0]=dp[i-1][0]+nums[i][0];
}
//给列赋值
for(int i=1;i<column;i++)
{
dp[0][i]=dp[0][i-1]+nums[0][i];
}
//dp过程
for(int i=1;i<row;i++)
{
for(int j=1;j<column;j++)
{
dp[i][j]=nums[i][j]+min(dp[i-1][j],dp[i][j-1]);
}
}
return dp[row-1][column-1];
}
};