数字三角形模型
在动态规划中，有三种基本情况，求最大值，最小值，数量
分析动态规划问题：
状态表示（通过集合的方式表示）：以数字三角形为例：f(i,j)，（i，j）表示从（1，1）到（i，j）的所有路径，属性是最大值。
状态计算：我们考虑如何对集合进行划分，然后可以通过一些方式计算出f(i,j)，比如该问题可以考虑如何走到（i，j）这个点，划分成从上边下来，或者从左边走到。这样就对集合进行了划分，并且可以保证（不重，不漏，可计算）。这里其实也可以假定上一层已知，一直计算到这一层，这可以抽象成一个图，从上一次可以计算成这一层，这就要求我们每次循环必须知道这一层的计算要用到的那一层，这也就可以体现出"动态规划"这四个字。我认为的动态规划在一定要求上就是可以根据一些已知条件，计算出一些未知条件，然后未知条件已知，在根据这些已知条件已知计算下去，然后知道计算出题目要求的条件。
模板题
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=10010,INF=0x3f3f3f3f;
int n;
int a[N][N];
int f[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
int t;
cin>>t;
a[i][j]=t;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=i+1;j++){
f[i][j]=-INF;
}
}
f[1][1]=a[1][1];
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
}
}
int ma=-INF;
for(int i=1;i<=n;i++){
if(f[n][i]>ma){
ma=f[n][i];
}
}
cout<<ma<<endl;
return 0;
}