数字三角形(DP)

问题：
　　给定一个由n行数字组成的数字三角形，如下图所示：

            7 
   　      3 8 
      　  8 1 0 
   　　  2 7 4 4 
　　    4 5 2 6 5 

　　试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。

输入：
　　第一行是数字三角形的行数，接下来 n 行是数字三角形中的数字。　　

　　比如：

　　5

　　7

　　3 8

　　8 1 0

　　2 7 4 4

　　4 5 2 6 5　　

输出：
　　输出这个最大值。

思路：从最低层向上递推，除最底层外，每一行每个点的最大值等于其本身加上下面一行所对应的左右两点的最大值
D[i][j] = max(D[i+1][j],D[i+1][j+1]) + D[i][j]；

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;


int MaxSum(int num){
    int i, j;
    for(i = num - 1; i >= 1; i--) //最底层 
        for(j = 1; j <= i; j++) {
            D[i][j] = max(D[i+1][j],D[i+1][j+1]) + D[i][j];
        }

    return D[1][1]; 
} 
int main(){
    int i,j;

    cin >> n;

    for(i=1; i<=n; i++) 
        for(j=1; j<=i; j++)
            cin >> D[i][j];

    cout << MaxSum(n) << endl;
}