听说这是经典dp
于是乎我用了贪心 记忆搜索
在贴代码之前还是讲一讲吧。
- dp、分治、递归、递推、搜索 的关系
很简单，没有关系 dp 是递推，是搜索的改版，是递归的进化体，是（在死亡的边缘大鹏展翅）分治的体现。
- 详解 水题解 数字三角形
首先排除贪心。
为什么？
看一眼样例吧，的确木有贪心策略。
但是，我们可以使用搜索愉快地玩耍。
那么具体怎么搜索呢？（好问题，我也不知道）
#include<bits/stdc++.h>
using namespace std;
int r,a[1010][1010],i,j,ans;
void dfs(int h,int l,int s){
if(h==r){
ans=max(ans,s);
return;
}
dfs(h+1,l,s+a[h][l]);
dfs(h+1,l+1,s+a[h][l]);
}
int main(){
memset(dp,-1,sizeof(dp));
cin>>r;
for(i=0;i<r;i++) for(j=0;j<=i;j++) cin>>a[i][j];
dfs(0,0,0);
return 0;
}
这就是最水的深搜（爆搜），不给注释了
不用试了，我交过，TLE*4。
神奇的记忆化
这也很简单。首先记忆化一定满足：
- 函数返回值仅与其参数有关
- 相同参数下的返回值相同
- 以返回值传递结果
有一个记忆数组（滑稽）
辣么，我们的答案就会要以返回值传递。
具体的思路也很简单，只要 洗洗睡吧其实要改很多 调整一下思路，你就会发现：
答案居然是 max(左边路的最大分数,右边路的最大分数)+自己的数
如果你还要问为什么，我也会 严肃 地回答你：
这里的左边路、右边路不是指一直向左走向右走，是本次左走之后所有的可以走的路（右边也一样）。
所以这也是显而易见的
所以就会很简单的开始你的记忆化。
实际上三个参数的记忆化很烦的（动不动爆空间），但是，因为最终答案是以返回值传递的，所以最初爆搜代码的参数 s 就可以丢掉了。
#include<bits/stdc++.h>
using namespace std;
int r,a[1010][1010],i,j,dp[1010][1010];
/*
* dp是记忆数组。
*
* h和l表示行、列
*/
int dfs(int h,int l){
if(dp[h][l]>-1) return dp[h][l];
// 如果记忆过就直接返回
if(h==r) dp[h][l]=a[h][l];
// 如果搜到底层就返回数字
else dp[h][l]=max(dfs(h+1,l),dfs(h+1,l+1))+a[h][l];
// 伪状态转移方程
return dp[h][l];
//快乐结束
}
int main(){
memset(dp,-1,sizeof(dp));//初始化，便于判断
cin>>r;
for(i=0;i<r;i++) for(j=0;j<=i;j++) cin>>a[i][j];
//输入完成
cout<<dfs(0,0);
return 0;
//标准结局（此结局非彼结局）
}
/*
* 题目数据不是很大，于是乎木有输入输出优化
*
* 码风不好我也没办法 QAQ
*/
辣么这道题就可以AC了，所以我也不写 dp 代码惹 其实是我不会dp
最后贴一张图，手动去除背景水印，所以比较亮（请佩戴墨镜）
这是一个算法区分图，里面的高级名词可以手动百度~
管理求过，第二次发题解（第一次发的题解误删了QAQ）
