线性DP:数字三角形
找路径从上到下找还是从下到上找，分析问题的方法 在于从上往下的话需要考虑从左边下来还是右边下来，那么在左右边界上需要考虑空白边界问题。
而从下往上找路径的时候就无需考虑边界判断问题。
| Dp问题 | 状态表示 f(i,j) | 集合 | 自下而上走到（i，j）位置的路径集合 | |||||
| - | ||||||||
| f(i,j)的值存的是什么 | 自下而上走到（i，j）位置的路径长max | |||||||
| - | ||||||||
| 状态计算 （其实质是集合的划分） | 划分 | 左边上来f(i+1,j)+w(i,j）-> f(i,j） | ||||||
| - | ||||||||
| 右边上来f(i+1,j+1)+w(i,j）-> f(i,j） | ||||||||
| - | ||||||||
#include<iostream>
#include<algorithm>
using namespace std;const int N = 510;int n;
int w[N][N], f[N][N];int main()
{cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)cin >> w[i][j];for (int i = 1; i <= n; i++)f[n][i] = w[n][i];//自底向上初始化Dp数组for (int i = n - 1; i; i--)//从倒数第二行开始，则开始时倒数第一行为i+1行for (int j = 1; j <= i; j++)//从左到右f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];//f(i,j)节点左下、右下取max加上f(i,j)点本身权重w(i,j)即可保存路径最大值。//顶点即为最大值cout << f[1][1] << endl;return 0;
}时间复杂度就是遍历一个二维数组，O(n²），1s内C++完成10^7~10^8次计算，500²远小于该数值，可以完成。
小结：说明遍历的顺序也是动态规划类问题的重点关注环节。