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];
    }
};
上一篇下一篇

猜你喜欢

热点阅读