有一个层数为 n(n≤1000)的数字三角形(如下图) 。从顶层开始向下走,每走下一级时,可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。
![](/static/upload/1614323726155808.png)
【输出样例】
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;
}