动规入门 - 数字三角形(从朴素递归到递推的四步优化)

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

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

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99。
输入：
　　第一行是数字三角形的行数，接下来 n 行是数字三角形中的数字。
　　比如：

输出：
　　输出这个最大值。

代码：

#include<iostream>
#include<algorithm>
using namespace std;

#define MAX 101
int a[MAX][MAX];

//一、笨方法：会产生重复计算,时间复杂度为 2的n次方
//仅有两条路走：向正下(x+1,y)或向右下(x+1,y+1)走
int GetMax1(int n, int x, int y) {
    return x >= n ? a[x][y] : max(GetMax1(n, x + 1, y), GetMax1(n, x + 1, y + 1)) + a[x][y];
}

//二、记忆递归型动规，让递归不会产生重复计算
int sum[MAX][MAX];
int GetMax2(int n, int x, int y) {
    if (sum[x][y] != -1) return sum[x][y];//已经计算过了，就直接返回
    sum[x][y] = (x >= n ? a[x][y] : max(GetMax2(n, x + 1, y), GetMax2(n, x + 1, y + 1)) + a[x][y]);
    return sum[x][y];
}

//三、递推,复杂度为 n的平方
int GetMax3(int n) {
    for (int i = n - 1; i >= 0; --i)
        for (int j = 0; j <= i; ++j)
            sum[i][j] = a[i][j] + max(sum[i + 1][j], sum[i + 1][j + 1]);
    return sum[0][0];
}

//四、递推的空间优化:不用额外空间存储，直接使用最后一行(即第n行)来存储
int GetMax4(int n) {
    for (int i = n - 1; i >= 0; --i)
        for (int j = 0; j <= i; ++j)
            a[n][j] = a[i][j] + max(a[n][j], a[n][j + 1]);
    return a[n][0];
}

int main() {
    int n;
    cin >> n;
    if (n<1 or n>MAX)
        return EXIT_FAILURE;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            cin >> a[i][j];

    cout << GetMax(n - 1, 0, 0) << endl;

    memset(sum, -1, sizeof(sum));//将sum初始化为 -1
    cout << GetMax2(n - 1, 0, 0) << endl;

    memcpy(sum[n - 1], a[n - 1], sizeof(a[n - 1]));//copy a[n-1] to sum[n-1].
    cout << GetMax3(n - 1) << endl;

    cout << GetMax4(n - 1) << endl;

    system("pause");
    return EXIT_SUCCESS;
}

详细解析可参考：
https://www.cnblogs.com/LYLtim/p/4286150.html

最后编辑于：2018.02.08 23:35:05