leetcode 120
来源：1-1 算法面试不仅仅是正确的回答问题
慕姐8741563
2018-12-20
看来完全没有人提问过这个问题。sad。我想请老师提供一些思路，或者说，矫正一下我的思路，所以我把我不明白的几点和我的想法写了下来：
（1）首先我就想到了搜索，因为斐波拉契的本质就是递归，搜索也是递归然后，您也说要我们先用递归。我把我的代码贴在下面：class Solution {
public:
vector<vector>ans;
int memo[500][500];
int sum;
int n;
int dfs(int i,int j,int sum)
{
// cout<<i<<" “<<j<<” "<<sum<<endl;
if(i==n||j>i)
{
return sum;
}
if(memo[i][j]!=0)
{
return memo[i][j];
}
sum=sum+ans[i][j];
int x=i+1;
int y=j;
if(y<0)
{
y=0;
}
int sum1=dfs(x,y,sum);
// cout<<sum1<<endl;
x=i+1;
y=j+1;
int sum2=dfs(x,y,sum);
// cout<<sum2<<endl;
if(sum1<sum2)
{
// cout<<"Hello"<<sum1<<" "<<sum2<<endl;
memo[i][j]=sum1;
return sum1;
}
else
{
memo[i][j]=sum2;
// cout<<"Hello2"<<sum1<<" "<<sum2<<endl;
return sum2;
}
}
int minimumTotal(vector<vector<int>>& triangle) {
// cout<<"Hello"<<endl;
memset(memo,0,sizeof(memo));
ans=triangle;
sum=ans[0][0];
n=triangle.size();
int ans1=dfs(0,0,0);
return ans1;
}
};
第一个问题就是记忆化搜索怎么做：我好像并不能像斐波拉契一样，开一个二维数组，存放的是经过这个点的最短路径。（如上），因为这里会涉及到一个路径更新的问题，并不能直接拿来用，所以我就不会做了。
第二个问题是怎么转化成最小问题，从最顶层看，我要求这一个三角形的最短路径（大意上），接着我就想转化成求第二层到最后一层的最短路径。加上第一层的最小值，但是这样并不行，因为路径是整体的，额，然后我就不知道做了。
希望bobo老师能稍微指点一下思路，感觉我的思路很欠缺。如果有什么我没说清楚的地方请老师提出，多谢！
2回答
-
liuyubobobo
2018-12-20
一个代码顶千言。请仔细研究这个代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0120-Triangle/cpp-0120/main2.cpp
其中的go是求出从顶到i, j位置的最小sum值。
请仔细比较这个实现和动态规划的实现，尤其是转移方程部分（他们是一样的！）。仔细理解记忆化搜索和动态规划的一致性确实很重要，说明你正在彻底掌握动态规划的路上！
至于你的第二个问题，我们的动态规划问题的状态不是这样设计的：）我们的动态规划dp[i][j]的意思也是从顶到i,j位置的最小sum值。最后在最后一排再求最小的sum值。所以，记忆化搜索是一样的，而不是状态定义中直接求出一层的最小值！（如果这样定义，确实搞不出来。为什么？，没有最右子结构了！）
请再仔细体会一下动态规划和记忆化搜索，他们的状态定义也是一致的！
加油！：）
00 -
慕姐8741563
提问者
2018-12-20
class Solution { public: vector<vector<int>>ans; int memo[500][500]; int sum; int n; void dfs(int i,int j,int sum) { if(i==n||j>i+1) { return ; } if(sum+ans[i][j]<memo[i][j]) { memo[i][j]=sum+ans[i][j]; sum=memo[i][j]; } else if(sum+ans[i][j]>=memo[i][j]&&memo[i][j]!=0x3f3f3f3f) { return ; } int x=i+1; int y=j; if(y<0) { y=0; } dfs(x,y,sum); x=i+1; y=j+1; dfs(x,y,sum); return; } int minimumTotal(vector<vector<int>>& triangle) { // cout<<"Hello"<<endl; for(int i=0;i<500;i++) { for(int j=0;j<500;j++) { memo[i][j]=0x3f3f3f; } } ans=triangle; sum=ans[0][0]; n=triangle.size(); dfs(0,0,0); int min1=0x3f3f3f; for(int i=0;i<n;i++) { if(memo[n-1][i]<min1) { min1=memo[n-1][i]; } } return min1; } };老师，以上是我新想的代码，AC了，但是动态规划的解法还是不知道做，感觉差一点点就能想到了，就是想不到。?
00
相似问题