题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
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
算法
(动态规划,线性DP) $O(n^2)$
从输入样例可以发现其实到第a[i][j]个点的最大距离在数组上的表示就是a[i-1][j]和a[i-1][j-1]中的大值加上a[i][j]。
但是这题与AcWing 1015. 摘花生有点区别,存在边界条件(不知道是不是这个意思)。即当点为a[i][1]或者a[i][i]时,到这个点的最大距离变成a[i-1][1]+a[i][1]或者a[i-1][i-1]+a[i][i]。想象力比较差的小伙伴可以动手画一下,就能理解了。
剩下的就是判断到非边界条件的点的最大值,然后排序一下数组第n行,取出最大值输出即可。
时间复杂度
emmm,不太会算
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int n,sum = -1e6;
int a[N][N],f[N][N];
int main()
{
cin >> n;
for(int l = 1; l <=n; ++ l)
{
int m = 1;
while(m <= l) cin >> a[l][m] , ++ m;
}
for(int i = 1; i <=n; ++ i)
{
for(int j = 1; j <=i; ++ j)
{
if(j == 1) f[i][j] = f[i - 1][j] + a[i][j];
else if( j == i) f[i][j] = f[i - 1][j - 1] + a[i][j];
else
f[i][j] = max(f[i - 1][j] , f[i - 1][j - 1]) + a[i][j];
}
}
for(int k = 1; k <=n; k++)
{
if( sum < f[n][k]) sum = f[n][k];
}
cout << sum << endl;
return 0;
}