题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
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
从上到下的分析: 要考虑边界问题
注意:因为 memset(f, 0x8f, sizeof f) 是将 f 的每一个字节设置为0x8f,而不是每一个元素。当第二个参数大于一个字节的最大值时,按照某种方式截断,所以 1e9 就 WA 了hhh
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=505;
const int INF=1e9;
int w[N][N],f[N][N];
int t;
int main(){
scanf("%d",&t);
for(int i=1;i<=t;i++){
for(int j=1;j<=i;j++){
scanf("%d",&w[i][j]);
}
}
memset(f,-0x3f3f3f3f,sizeof(f));//因为权值可能是赋值,找最大值呢,超出边界部分要等于负无穷,要全部赋值为负无穷,这里的参数不可以是-1e9,只能是0x3f3f3f3f,它是按字节赋值的,时间复杂度是O(n),跟用for赋值的复杂度是一样的
f[1][1]=w[1][1];
for(int i=2;i<=t;i++){ //从第二行开始,如果从第一个开始,结果一直会是负无穷
for(int j=1;j<=i;j++){
f[i][j]=max(f[i-1][j-1],f[i-1][j])+w[i][j];
}
}
int res=-INF;
//因为到第t层有很多个出路,要看看那个出路的值最大,1015摘花生那个题是因为可以从左边过来,
//可以从上面过来,它又是矩形的形状,终点在最右下方,就一个可能终点,这个题有t个可能终点,要遍历一下找最大的那个
for(int i=1;i<=t;i++){
res=max(f[t][i],res);
}
printf("%d\n",res);
return 0;
}
从下到上的分析: 不必考虑边界问题
状态表示:
集合:从底(n,j)到(i,j)的所有路线
属性:所有路线的数字和最大值
状态计算:(本质就是集合的划分)
从右下方过来:f[i+1][j+1]+w[i][j]
从左下方过来:f[i+1][j]+w[i][j]
代码如下:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int t,n,m;
const int N=505;
int w[N][N],f[N][N];
int main(){
scanf("%d",&t);
for(int i=1;i<=t;i++){
for(int j=1;j<=i;j++){
scanf("%d",&w[i][j]);
}
}
for(int i=t;i>=1;i--){ //也可正着遍历
//第t行时,正好全局变量f[][]为0,不用改成负无穷了,经过max函数,直接f[t][j]=w[t][j]了,也不用再用for循环赋了
for(int j=i;j>=1;j--){
f[i][j]=max(f[i+1][j+1],f[i+1][j])+w[i][j];
}
}
printf("%d\n",f[1][1]); //就一个可能终点(1,1),所以不用向第一种方法一样再遍历找最大值了
return 0;
}