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.
问题:大数据的时候TLE,问题搜索的时候,走了很多重复的子路径
所以不能进行DFS(DFS本质上是暴力),而应该DP
DP[i,j] =代表从A[0,0]到A[i,j]的path个数
DP[i,j] = DP[i-1,j] + DP[i,j-1]接下来自底向上或者memorize的方式都OK
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > dp = grid;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size();j++){
if (i > 0 && j > 0){
dp[i][j] = min(dp[i][j -1],dp[i -1][j]) + grid[i][j];
}else if (i > 0){
dp[i][j] = dp[i -1][j] + grid[i][j];
}else if (j > 0){
dp[i][j] = dp[i][j -1] + grid[i][j];
}else{
dp[i][j] = grid[i][j];
}
}
}
return dp[grid.size() -1][grid[0].size() -1];
}
};
class Solution {
public:
void dp1(int m, int n){
vector<int> dp(n.size(),1);
for(int i = 1; i < m; i++){
for(int j = 0; j < n; j++){
//dp[i][j] = dp[i-1][j] + dp[i][j-1];
if (j) dp[j] = dp[j] + dp[j-1];
}
}
return dp[dp.size() -1];
}
//继续优化到一个2个变量,问题是需要保存上一次的i-1的dp[j]的值,而用ans pre两个变量只能保存到当前的i的dp[j]的值
//继续优化失败
void dp2(int m, int n){
int ans = 1, pre = 0;
for(int i = 1; i < m; i++){
for(int j = 0; j < n; j++){
if (j){
ans = ans + pre;
}else{
ans = 1;
}
pre = ans;
}
}
return ans;
}
int uniquePaths(int m, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return dp1(m,n);
}
};
原文链接: https://www.cnblogs.com/kwill/p/3185454.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/95551
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!