题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
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++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;
int a[N][N];
int f[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
//初始化注意边界从0开始,j到i+1是因为最右边的点会用到他右上方的点更新
for(int i=0;i<=n;i++){
for(int j=0;j<=i+1;j++){
f[i][j]=-INF;
//f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
//cout<<f[i][j]<<" !!! ";
}
}
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]+a[i][j],f[i-1][j]+a[i][j]);
//cout<<f[i][j]<<" !!! ";
}
}
//最底层找一个最大值
int res=-INF;
for(int i=1;i<=n;i++){
res=max(res,f[n][i]);
}
cout<<res<<endl;
}
python 代码
INF=float('-inf')
n=int(input())
s=[[0]]#加上[0]使得s纵坐标坐标从1开始
f=[[INF]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
a=[0]+list(map(int,input().split()))#加上[0]使得s横坐标从1开始
s.append(a)
#print(s)
f[1][1]=s[1][1]
for i in range(2,n+1):
for j in range(1,i+1):
f[i][j]=max(f[i-1][j-1]+s[i][j],f[i-1][j]+s[i][j])
res=INF
for i in range(1,n+1):
res=max(res,f[n][i])
print(res)