洛谷P1216—[USACO1.5][IOI1994]数字三角形 Number Triangles题解 DP+dfs!
传送门
首先，这个题用贪心是肯定做不出来滴！
那么用什么方法做呢？
我要是知道我就不看题解了！
思路是——
状态转移方程：
[f[x][y]=a[x][y]+max(f[x+1,y],f[x+1,y+1])
]
从最上层开始向下搜索，搜到最底层后回溯就可以了
不要忘记判断边界
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int r,a[1005][1005];
int mem[1005][1005];//记忆化数组
int dfs(int x,int y)
{
if(x>=r-1)//边界判断
return a[x][y];
if(mem[x][y]>-1)return mem[x][y];//记忆化
return mem[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));//状态转移方程
}
int main()
{
memset(mem,-1,sizeof(mem));//初始化记忆数组
cin>>r;
for(int i=0;i<r;i++)
for(int j=0;j<=i;j++)cin>>a[i][j];//输入数组
cout<<dfs(0,0);//从最上层开始搜
return 0;
}