动态规划分析法

y总的动态规划分析法。
总得来说，对于一个动态规划问题，可以分为两个方面进行分析，分别为状态表示和状态计算两部分。
状态表示是对动态规划数组dp[i,j]进行分析，分为集合和属性，集合来分析我们的动态规划数组表示的是什么，属性即要从集合获得什么样属性的元素，如最大最小值。
状态计算是根据问题进行具体分析状态dp[i,j]可以由什么状态转移而来从而获得状态转移方程。
例题：
数字三角形：https://www.acwing.com/problem/content/900/
分析：


代码：

#include<bits/stdc++.h>
using namespace std;
const int N =505;
const int inf = INT_MAX/2;
int a[N][N];
int dp[N][N];
int n;
int main(void)
{
     cin>>n;
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=i;j++)
         {
             cin>>a[i][j];
         }
     }
     for(int i=0;i<=n;i++)
     {
         for(int j=0;j<=i+1;j++)
         {
             dp[i][j] =-inf;//对边界进行处理
         }
     }
     dp[1][1] = a[1][1];
     for(int i=2;i<=n;i++)
     {
         for(int j=1;j<=i;j++)
         {
             dp[i][j] = max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
         }
     }
     int ans =-inf;
     for(int i=1;i<=n;i++)
     {
         ans =max(ans,dp[n][i]);//找到最后一行的最大值
     }
     cout<<ans<<endl;
}