CP003174 DP题解

这道题是经典的动态规划题目，有三种方法来做：

• 搜索（超时）
• 记忆化搜索
• 动态规划

在这里，本人主要介绍动态规划（Dymanic Programming,DP）的做法。

1. 确定状态：本题题目使用二维数组，故状态为dp[i][j]。
2. 确定状态转移方程：所有的dp元素都是由该元素下面的两个元素的权值中的最大权值加上自己，故其状态转移方程便是：dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
3. 确定边界条件：该图的底层是最下面的一行元素，从倒数第2行往上递推即可。
4. 程序实现：

#include<bits/stdc++.h>
#define io freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
#define ll long long
#define ull unsigned long long
using namespace std;
// variables setting
const int N=110;
int n,i,j;
int dp[N][N];
// functions(others) defining
// the program subject
void program()
{
    cin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            cin>>dp[i][j];
    for(i=n-1;i>=1;i--)
    {
        for(j=1;j<=n;j++)
        {
            dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
        }
    }
    cout<<dp[1][1]<<endl;
}
// the main function
int main()
{
    //io;
    program();
    return 0;
}