首页 > 代码库 > [LeetCode] Minimum Path Sum
[LeetCode] 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.
如果不是必须用stack，尽量不要用stack计算，因为总是会Time Limit Exceeded，就像下面代码：
class Solution {public: int minPathSum(vector<vector<int> > &grid) { int m = grid.size(); if(m<=0) return 0; int n = grid[0].size(); stack<pair<pair<int,int>,int>> s; pair<int,int> temp(0,0); pair<pair<int,int>,int> rowCol_PathSum(temp,grid[0][0]);//存放行列值，以及从右上到此位置的PathSum值 s.push(rowCol_PathSum); int minPaSum = -1; int row = 0,col = 0; while(!s.empty()){ rowCol_PathSum = s.top(); s.pop(); row = rowCol_PathSum.first.first; col = rowCol_PathSum.first.second; int pathSum = rowCol_PathSum.second; if(row==m-1 && col == n-1) { if(minPaSum==-1 || rowCol_PathSum.second<minPaSum) minPaSum = pathSum; continue; } if(row<m-1) { rowCol_PathSum = make_pair(make_pair(row+1,col),pathSum+grid[row+1][col]); s.push(rowCol_PathSum); } if(col<n-1) { rowCol_PathSum = make_pair(make_pair(row,col+1),pathSum+grid[row][col+1]); s.push(rowCol_PathSum); } }//end while return minPaSum; }};
看下面的方法，只需遍历一遍整个数组。DP
思路：定义一个与原数组一样大小的数组，数组(i,j)位置记录从(0,0)到(i,j)最小路径和，则要计算的从左上到右下的最小路径和就是所定义数组的右下角的元素：
class Solution {public: int minPathSum(vector<vector<int> > &grid) { vector<vector<int> > minPathSumm = grid; int row = grid.size(); if(row<=0) return 0; int col = grid[0].size(); int i = 1; while(i<col) { minPathSumm[0][i] = grid[0][i]+minPathSumm[0][i-1]; i++; } int j=1; while(j<row) { minPathSumm[j][0] = grid[j][0]+minPathSumm[j-1][0]; j++; } for(int i=1;i<row;i++) { for(int j=1;j<col;j++) { minPathSumm[i][j] = min(minPathSumm[i-1][j],minPathSumm[i][j-1])+grid[i][j]; } } return minPathSumm[row-1][col-1]; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。