经典算法

动态规划-数塔

有一个层数为 n（n≤1000）的数字三角形（如下图） 。从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。

【输出样例】

23
【参考程序】

//小牛编程
#include <bits/stdc++.h>
using namespace std;

int arr[7][7] = {{0, 0, 0, 0, 0, 0, 0}, 
                 {0, 1, 0, 0, 0, 0, 0},
                 {0, 6, 3, 0, 0, 0, 0}, 
                 {0, 8, 2, 6, 0, 0, 0},
                 {0, 2, 1, 6, 5, 0, 0}, 
                 {0, 3, 2, 4, 7, 6, 0},
                 {0, 0, 0, 0, 0, 0, 0}};

int f[1001][1001];

int main() {
    int n = 5; //中间是5行5列数组

    for (int i = 1; i <= n; ++i)
        f[n][i] = arr[n][i];

    for (int i = n - 1; i >= 1; --i)
        for (int j = 1; j <= i; ++j)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + arr[i][j];

    cout << f[1][1] << endl;

    return 0;
}