HDU 2048 号碼塔(DP)

号碼塔

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

Total Submission(s): 20786    Accepted Submission(s): 12486

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

最簡單的DP。能夠簡單的分析子問題，最上層的和最大依賴于其下方的兩個數為根節點的數塔的最大值，是以能夠從下向上一次DP上來，每次選擇左右子數塔中和大的那一個就能夠了。

版權聲明：本文部落客原創文章。部落格，未經同意不得轉載。