给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 nn,表示数字三角形的层数。
接下来 nn 行,每行包含若干整数,其中第 ii 行表示数字三角形第 ii 层包含的整数。
输出格式
输出一个整数,表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
- 解法一:(从上往下转移)
f[i,j]表示从起点到[i,j]这个点的最大路径和
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
const int INF=1e9;
int f[N][N];
int q[N][N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <=i; j ++ ){
cin >> q[i][j];
}
}
//把数组中的各个值初始化为负无穷 因为数组中数可能为负数
for (int i = 0; i <= n; i ++ ){
for (int j = 0; j <=n; j ++ ){
f[i][j]=-INF;
}
}
f[1][1]=q[1][1];
for (int i = 2; i<= n; i ++ ){
for (int j = 1; j<=i; j ++ ){
f[i][j]=max(f[i-1][j]+q[i][j],f[i-1][j-1]+q[i][j]);
}
}
int res=-INF;
//输出最后一行中的最大值
for (int i = 1; i <= n; i ++ ){
res = max(res,f[n][i]);
}
cout << res<<endl;
return 0;
}
解法二:(从下往上转移)
f[i,j]表示[i,j]点到底边元素的最大路径和
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int f[N][N];
int q[N][N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <=n; i ++ ){
for (int j = 1; j <=i; j ++ )
cin >> q[i][j];
}
//初始化
for (int i = 1; i <= n; i ++ ) f[n][i]=q[n][i]; ////f[i][j]表示q[i][j]这个点到底边元素的最大路径和
for(int i=n-1;i>=1;i--){ //从倒数第二行开始向上枚举
for(int j=1;j<=i+1;j++){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+q[i][j];
}
}
cout << f[1][1]<<endl;
return 0;
}