题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
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
算法1
(DP) $空间复杂度 O(n)$
利用DP,边输入边DP即可。
每个标号为i的结点的最大代价只与上一行结点中标号为i和i-1的结点有关。
注意i=0时只与上一行的i=0有关,i=n时只与上一行的i=n-1有关。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#define lines 500
int dp[lines],N,sum,temp,dp_t1,dp_t2;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>N>>dp[0];
dp_t1=dp[0];
for(int i=1;i<N;++i){
std::cin>>temp;
dp[0]=temp+dp_t1;
for(int j=1;j<i;++j){
std::cin>>temp;
if(dp[j]>dp_t1){
dp_t1=dp[j];
dp[j]+=temp;
}
else{
dp_t2=dp[j];
dp[j]=temp+dp_t1;
dp_t1=dp_t2;
}
}
std::cin>>temp;
dp[i]=temp+dp_t1;
dp_t1=dp[0];
}
sum=dp[0];
for(int i=1;i<N;++i){
temp=dp[i];
if(sum<temp)
sum=temp;
}
std::cout<<sum;
return 0;
}