先放题目
P1216
动态规划又称dp一般需要一下几步
1. 定义状态
2. 初始化
3. 状态转移方程
4. 查找答案
我们根据上面的步骤，解决这个问题。
1. 定义状态： dp_{i,j} 表示走到 (i,j) 得到的最大数字总和。
2. 初始化：很明显 dp_{1,1}=a_{1,1} ，其中 a_{i,j} 是$(i,j)$ 上的数字。
3. 状态转移方程：它可以向下方或右下方走，那么很明显 (i,j) 可以从 (i-1,j) 或 (i-1,j-1) 走过来，状态转移方程就是 dp_{i,j}=max_{dp_{i-1,j-1}}^{dp_{i-1,j}}+a_{i,j} 。
4. 查找答案：最后走到最后一行所以答案就是 \displaystyle\sum_{i=1}^{n}max_{dp_{n,i}} 。
那么最终代码如下（这里我只放核心代码）：
for(int i=2;i<=n;++i)
for(int j=1;j<=i;++j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
for(i=1;i<=n;++i) Max=max(Max,a[n][i]);
cout<<Max;