美文网首页
leetcode 64最小路径和

leetcode 64最小路径和

作者: 橘子煲汤 | 来源:发表于2019-02-14 22:43 被阅读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];
    }
};

相关文章

  • LeetCode 64. 最小路径和 | Python

    64. 最小路径和 题目来源:力扣(LeetCode)https://leetcode-cn.com/proble...

  • 【D13】最小路径和 & 爬楼梯 (LC 64&70)

    64. 最小路径和[https://leetcode-cn.com/problems/minimum-path-s...

  • [LeetCode]64、最小路径和

    题目描述 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。...

  • LeetCode 64 最小路径和

    64. 最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总...

  • Leetcode 64 最小路径和

    最小路径和 题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和...

  • leetcode 64最小路径和

    很简单的题目 多打了一个等号 结果找错找了半天 也是使用了dp来完成这个题目这应该算是一道用来比较好理解dp的一道题目

  • Leetcode-64:最小路径和

    描述:给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说...

  • Leetcode64最小路径和

    题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明...

  • leetcode#64 最小路径和

    题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说...

  • leetcode_64最小路径和

    直接在原矩阵上改数据,控制第一行和第一列更新为当前值和前面或上面的值累加,其他位置则判断从上面还是左边的值更小并累...

网友评论

      本文标题:leetcode 64最小路径和

      本文链接:https://www.haomeiwen.com/subject/cmqueqtx.html