HDU2084_數塔【簡單題】【數塔】

數塔

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 22488    Accepted Submission(s): 13555

Problem Description

在講述DP算法的時候，一個經典的樣例就是數塔問題，它是這樣描寫叙述的：

有例如以下所看到的的數塔。要求從頂層走究竟層，若每一步僅僅能走到相鄰的結點，則經過的結點的數字之和最大是多少？

已經告訴你了。這是個DP的題目。你能AC嗎?

Input

輸入資料首先包含一個整數C,表示測試執行個體的個數。每一個測試執行個體的第一行是一個整數N(1 <= N <= 100)，表示數塔的高度，接下來用N行數字表示數塔。當中第i行有個i個整數，且全部的整數均在區間[0,99]内。

Output

對于每一個測試執行個體，輸出可能得到的最大和，每一個執行個體的輸出占一行。

Sample Input

1

5

7

3 8

8 1 0 

2 7 4 4

4 5 2 6 5

Sample Output

30

Source

2006/1/15 ACM程式設計期末考試

題目大意：比較好了解

思路：若從上往下考慮的話，每次有兩個選擇，N層數塔就有2^(N-1)種方案，

周遊一邊不科學。換種方式，從下往上考慮，每次比較臨近兩個數的大小，讓較

大的數往上加。這樣每次選擇得到的都是最優的情況，逐層上移累加。終于加到

頂部的時候，得到的結果就是最優的，即最大的。