题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数n,表示数字三角形的层数。
接下来n行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数,表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
算法
非常经典的题目,很多算法书上都会出现。可以搜索,也可以动态规划。
处理时可以选择从上往下的顺序处理,但从下往上处理起来更方便些。
C++代码:从下往上(1)
#include <iostream>
using namespace std;
const int N = 510;
int n;
int a[N][N], f[N][N];//a[][]记录数字三角形,f[][]记录动态规划状态
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)//输入三角形数字
for (int j = 0; j <= i; ++j)
scanf("%d", &a[i][j]);
for (int i = n - 1; i >= 0; --i)//从下往上遍历n层
for (int j = 0; j <= i; ++j)//每层从左往右遍历
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];//取下侧和右下的最大值
printf("%d\n", f[0][0]);
return 0;
}
C++代码:从下往上(2) 迭代使用一个数组
#include <iostream>
using namespace std;
const int N = 510;
int f[N][N];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
cin >> f[i][j];
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]);
cout << f[1][1] << endl;
return 0;
}
从上往下
#include <iostream>
using namespace std;
const int N = 510, INF = 1e9;//INF:边界值,因为从上往下需要边界
int n;
int a[N][N];
int f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
scanf("%d", &a[i][j]);
for (int i = 0; i <= n; ++i)//从0开始:为防止计算时数组越界,人为在“外”多围一圈边界
for (int j = 0; j <= i + 1; ++j)//0、i+1:边界
f[i][j] = -INF;
f[1][1] = a[1][1];
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= i; ++j)
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
int res = -INF;
for (int i = 1; i <= n; ++i) res = max(res, f[n][i]);//在第n层寻找最大值
printf("%d\n", res);
return 0;
}