题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2084

题目要求:

image.png

做题思路:

当我看到这个题第一个想法就是使用贪心算法，于是试了一下，发现数字之和并不是最大的，后来才发现贪心算法只能局部求最优解，因此需要用动态算法。
首先先看图画出数值之和最大的一条路线：9->12->10->18->10

那么是怎么得出这条路线的呢？

答：从顶点出发时选择向左走还是向右走，取决于是向左走能取到最大值还是向右走能取到最大值，所以在选择之前必须要先求出左右两条路径的值。
我刚开始的思路是从上往下求路径，如图：

image.png

得出一条规律方程：a[ i ][ j ] = a[ i ][ j ] + Max(a[ i+i ][ j ] , a[ i+1 ][ j ])

代码:

#include <iostream>
using namespace std;
int main() {
    int a[100][100];
    int i,j,m,n;
    cin>>m;
    while(m-- > 0) {
        cin>>n;
        for (i = 0;i < n;i++) {
            for (j = 0;j <= i;j++) {
                cin>>a[i][j];
            }
        }
        for (i = n-1;i >= 0;i--) {
            for (j = 0;j <= i;j++) {
                a[i][j] += max(a[i+1][j],a[i+1][j+1]);
            }
        }
        cout<<a[0][0]<<endl;
    }
}