题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
代码实现
#include <iostream>
using namespace std;
const int N = 510, INF = 1e9;
int f[N][N], a[N][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 ++ )
for (int j = 0; j <= i + 1; j ++ )
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], f[i-1][j-1]) + a[i][j];
int res = -INF;
for (int i = 1; i <= n; i ++ ) res = max(f[n][i], res);
printf("%d", res);
return 0;
}
分析
要找到整个数字三角形的最大值,我们可以描述为去找从三角形第一行第一列(a[1][1])到三角形最后一行第?列(a[n][j]),这里用问号表示我们不知道最大值具体在哪里。
我们以从第一行第一列走到第i行第j列来为例,能够走到 a[i][j]
的位置只有上面 a[i-1][j]
和左上角a[i-1][j-1]
两类,也是就是说每个位置只有对应位置的左上角和上一格来决定走到本格的最大值,同理,每个格子都满足(a[1][1] 不满足,因为它是最顶上的格子)。
我们这里设 f[i][j]
表示走到 a[i][j]
的最大值,所以根据分类原理有: f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]
,其中 f[1][1] = a[1][1] // 第一个格的最大值只能是第一个数值
在实现这道题目时,我们发现有负数数据,零大于负数,所以,我们需要单独的对 f 数据进行单独的初始化,具体代码如下:
for (int i = 0; i <= n; i ++ ) //注意下标从 0 开始,因为 i - 1!!!
for (int j = 0; j <= i + 1; j ++ )
f[i][j] = -INF;
哈哈哈,自顶一个~