AcWing 898. 基础课二刷之第53题加强巩固 数字三角形*
原题链接
简单
作者:
Snow_raw
,
2021-08-20 17:45:44
,
所有人可见
,
阅读 174
题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
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(经典数塔)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int INF=-1e9;
int f[N][N];
int a[N][N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)for(int j=0;j<=i+1;j++)f[i][j]=INF;//注意j从0到i+1,因为数值可能<0如果j=0和j=i+1没初始化一个很小的数,会影响状态转移。
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
int x=INF;
for(int i=1;i<=n;i++)x=max(x,f[n][i]);
cout<<x<<endl;
return 0;
}