在講述DP算法的時(shí)候，一個(gè)經(jīng)典的例子就是數(shù)塔問題，它是這樣描述的： 有如下所示的數(shù)塔，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過的結(jié)點(diǎn)的數(shù)字之和最大是多少？
已經(jīng)告訴你了，這是個(gè)DP的題目，你能AC嗎?

數(shù)塔

Input

輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測試實(shí)例的個(gè)數(shù)，每個(gè)測試實(shí)例的第一行是一個(gè)整數(shù)N(1 <= N <= 100)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個(gè)i個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間[0,99]內(nèi)。

Output

對(duì)于每個(gè)測試實(shí)例，輸出可能得到的最大和，每個(gè)實(shí)例的輸出占一行。

Sample Input

1

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Sample Output

30

狀態(tài)量dp[i][j]表示到這個(gè)結(jié)點(diǎn)為止的最大和，其中i,j分別表示橫縱坐標(biāo)，為保證i-1不會(huì)越界，這里從1開始讀入數(shù)組：

for(int i=1;i<=N;i++)cin>>a[i][j];

狀態(tài)轉(zhuǎn)移方程：

dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

從上到下對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行狀態(tài)轉(zhuǎn)移：

for(int i=1;i<=N;i++)

 for(int j=1;i<=i;j++)

 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];

最后，遍歷最后一行，找到最大的數(shù)字和：

for(int j=1;i<=n;j++)

 maxx=max(maxx,dp[n][j]);

完整代碼：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int a[105][105],dp[105][105];
int main()
{
    int c,n,maxx;
    cin>>c;
    while(c--)
    {
        memset(dp,0,sizeof(dp));
        maxx=0;
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++) cin>>a[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
        for(int j=1;j<=n;j++)
            maxx=max(maxx,dp[n][j]);
        cout<<maxx<<endl;
    }
    return 0;
}