喂，你都趴在地上
半小時了，螞蟻有
那么好看嗎？
       /
STO . OPZ

你瞧，它在前進的路上
有很多種選擇，它不知
道哪條路上有食物...
            /
STO .OPZ
           . .
          \█/
           ○
           ?
          7
         / \
        3  8
       / \ / \
      8  1  0
    / \ / \ / \
   2  7   4  4
 / \ / \ / \ / \
4  5   2  6   5

         ○
        /█\
         ' '

一只螞蟻從n行的數字三角形頂部出發往下爬，只能往左下或右下爬，問如何爬才能讓它經過的數字和最大？

【輸入】

第一行一個整數n，表示三角形行數

接下來的n行是數字三角形

【輸出】

經過的數字總和最大值

【樣例輸入】

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

【樣例輸出】

30

【輸出說明】

7+3+8+7+5=30

題解：

我的第一反應是搜索，但是......T！L！E！

因此我換了一種思路：用動態規劃。

從頂部出發和從底部出發是一樣的，

每個頂點更新為當前頂點的值加上下面兩個頂點的值的最大值，從下往上搜索。

動規思路如下：

2 7 4 4        ==>   7 12 10 10

4 5 2 6 5              4  5   2   6   5

8 1  0          ==>   20  13  10

7 12 10 10            7   12  10    10

3    8           ==>    23  21

20  13  10              20 13 10

7                 ==>    30

23  21                   23 21

因此答案為30。

上代碼

 1 #include<iostream>
 2 using namespace std;
 3 int a[105][105],b[105][105];
 4 int n;
 5 int main()
 6 {
 7     cin>>n;
 8     int i,j;
 9     for(i=1;i<=n;i++)
10         for(j=1;j<=i;j++)
11             cin>>a[i][j];
12     for(i=1;i<=n;i++)
13         b[n][i]=a[n][i];
14     for(i=n-1;i>=1;i--)
15         for(j=1;j<=i;j++)
16             b[i][j]=a[i][j]+max(b[i+1][j],b[i+1][j+1]);
17     cout<<b[1][1];
18     return 0;
19 }