經典動态規劃基礎題-三角形最大和問題

三角形最大和問題

time limit:1000ms memory limit:65536k

total submit:79 accepted:22

description

現在經常有一些數學問題困擾着小明。有如下一個三角形，

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

小明想求出從頂至底的某處的一條路徑，使該路徑所經過的數字的總和最大。現在想請你編一個程式實作這個問題。

說明：

（1）每一步可沿左斜線向下或右斜線向下；

（2）1＜三角形行數≤100;

（3）三角形中的數字為0,1,...,99。

input

輸入有多個執行個體。每個測試用例的第一行是三角形的行數n，接下來是n行數字，每行數字的個數由1開始，依次加1。

output

輸出每個測試用例的最大和（整數），每行1個。

sample input

5

sample output

30

source

//最最基礎，最最經典的動态規劃入門題