首页 > 代码库 > 【LeetCode】Minimum Path Sum
【LeetCode】Minimum Path Sum
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.
解题思路：
典型的动态规划。开辟m*n的矩阵minV，minV[i][j]存放从首元素(grid[0][0])到当前元素(grid[i][j])的最短路径长度。
对于每个元素来说，路径是从上或者从左边来的。
也就是说minV[i][j] = min(minV[i-1][j]+minV[i][j-1]) + grid[i][j]。
别忘了初始化第一行第一列。
class Solution {public: int minPathSum(vector<vector<int> > &grid) { int m = grid.size(); int n = grid[0].size(); //DP，存放从首元素到该元素的最短路径 vector<vector<int> > minV; minV.resize(m); for(vector<vector<int> >::size_type st = 0; st < m; st ++) minV[st].resize(n); minV[0][0] = grid[0][0]; //第一列初始化 for(vector<vector<int> >::size_type st = 1; st < m; st ++) minV[st][0] = minV[st-1][0] + grid[st][0]; //第一行初始化 for(vector<int>::size_type st = 1; st < n; st ++) minV[0][st] = minV[0][st-1] + grid[0][st]; for(vector<vector<int> >::size_type st1 = 1; st1 < m; st1 ++) { for(vector<int>::size_type st2 = 1; st2 < n; st2 ++) { minV[st1][st2] = min(minV[st1-1][st2],minV[st1][st2-1])+grid[st1][st2]; } } return minV[m-1][n-1]; }};
【LeetCode】Minimum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。