leetcode 64最小路径和

很简单的题目 多打了一个等号 结果找错找了半天 也是使用了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];
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 描述:给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说...
    大数据Zone阅读 1,072评论 0 1
  • 第六章:绝地反击 倪小冰 我一边和尧伊交谈,一边想道:我一定要坚强,保护好女孩子。 我们终于到了一楼,我一边环顾四...
    DXZ神陨魔翎吖阅读 1,852评论 0 3
  • 高三暑假时我和小麦在南方的一个工厂打暑期工,她比我大三岁却是第一次出远门,动身的前一天晚上我在收拾东西,她感...
    徐琛笛阅读 3,030评论 1 4
  • 一个叫七七的孩子 撅起他的小嘴巴 给小女孩深情的一吻 小女孩欢喜又害羞 那深情的一吻 犹如雪莲花一般 含着无尽的娇...
    鸣鸥阅读 1,852评论 1 3