三、动态规划（1）-数学三角形

数学三角形

将所有的maxSum初始化为-1，然后递归计算然后将值保留其中，如果已经计算过就直接返回，否则的话就计算下面的返回最大值。

另一种思路：

从下往上计算，将每一层计算的值保留在数组中，则可以得到最终的值。只需一遍计算。最下面一层不用计算。

#include <iostream>
#include<algorithm>

using namespace std;

#define MAX 101

int D[MAX][MAX];
int  n;
int * maxSum;

int main(){
    int i, j;
    cout << "输入三角形行数：";
    cin >> n;
    cout << endl;
    cout << "输入三角形：" << endl;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; ++j){
            cin >> D[i][j];
        }
    }
    maxSum = D[n];
    for (i = n - 1; i >= 1; --i)
    {
        for (j = 1; j <= i; ++j)
            maxSum[j] = max(maxSum[j], maxSum[j + 1]) + D[i][j];
    }

    for (i = 1; i <= n; ++i)
        {
            for (j = 1; j <= i; ++j)
                cout << D[i][j] << " ";
            cout << endl;
        }
    cout << "maxSum(1,1): " << maxSum[1] << endl;
}

【总结】：