HDU 2084 数塔（动态规划入门）

传送门

中文题就不给大家翻译了（手动滑稽），反正大家都看得懂。

这是一道动态规划入门的题目，只需要找出状态转移方程即可。

状态方程：dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j])(dp[i][j]表示从第i层第j个数开始搜能得到的最大数）

代码如下：

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int t,n,dp[105][105],a[105][105];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 0;i < n; i++)
            for(int j = 0;j <= i; j++)
                scanf("%d",&a[i][j]);
        memset(dp,0,sizeof(dp));
        for(int i = 0;i < n; i++)
            dp[n-1][i] = a[n-1][i];
        for(int i = n - 2;i >= 0; i--)
        {
            for(int j = 0;j <= i; j++)
            {
                dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j];
            }
        }
        printf("%d\n",dp[0][0]);
    }
    return 0;
}