首页 > 代码库 > 【LeetCode】064. Minimum Path Sum
【LeetCode】064. Minimum Path Sum
题目:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
题解:
Solution 1 ()
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = (int) grid.size(), n = (int) grid[0].size(); vector<long> dp(n,INT_MAX); dp[0] = grid[0][0]; for(int i=0; i<m; ++i) { for(int j=0; j<n; ++j) { if(j > 0) dp[j] = min(dp[j] + grid[i][j], dp[j-1] + grid[i][j]); else if(i>0) dp[j] = dp[j] + grid[i][j]; } } return dp[n-1]; } };
边界的第二种处理方法:因为Solution 1 中dp初始化为最大值,故需要考虑溢出情况,所以用long整型。这个就初始化为int整型。
Solution 2 ()
class Solution { public: int minPathSum(vector<vector<int>>& nums) { int m = (int) nums.size(); int n = (int) nums[0].size(); vector<int> v (n,0); for (int i=0; i<m; ++i) { for (int j=0; j<n; ++j) { if (i>0) v[j] = nums[i][j] + ((j>0) ? min(v[j], v[j-1]) : v[j]); else v[j] = nums[i][j] + ((j>0) ? v[j-1] : 0); } } return v[n-1]; } };
解法没变,就是边界的处理上不一样,这个是先初始化边界了。
Solution 3 ()
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int dp[grid.size()][grid[0].size()]; dp[0][0] = grid[0][0]; // init first row for(int i = 1; i < grid[0].size(); i ++){ dp[0][i] = dp[0][i-1] + grid[0][i]; } // init first col for(int i = 1; i < grid.size(); i ++){ dp[i][0] = dp[i-1][0] + grid[i][0]; } for(int i = 1; i < grid.size(); i ++){ for(int j = 1; j < grid[0].size(); j++){ dp[i][j] = dp[i - 1][j] < dp[i][j-1]? dp[i - 1][j] + grid[i][j] : dp[i][j-1] + grid[i][j]; } } return dp[grid.size() - 1][grid[0].size() -1]; } };
【LeetCode】064. Minimum Path Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。