数字三角形模型
以数字三角形这个题为原型的所有题型。
AcWing 898.数字三角形
原题链接：https://www.acwing.com/problem/content/900/
解题思路
将这个数字三角形看成一个矩阵，然后DP分析
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
const int INF = 1e9;
int f[N][N],a[N][N];
int n;
int main()
{
scanf("%d",&n);
for(int i = 0; i <= n; i++)
for(int j = 1; j <= i;j ++)
scanf("%d",&a[i][j]);
// 因为存在负数，所以两边也要初始化为负无穷
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= i + 1; j ++)
f[i][j] = -INF;
f[1][1] = a[1][1];
for(int i = 2; i <= n; i ++)
for(int j = 1; j <= i; j ++)
f[i][j] = a[i][j] + max(f[i-1][j-1],f[i-1][j]);
int res = -INF;
for(int j = 1; j <= n; j ++) res = max(res,f[n][j]);
printf("%d",res);
return 0;
}