AcWing 898. 数字三角形
原题链接
简单
作者:
YAX_AC
,
2024-02-12 21:43:02
,
所有人可见
,
阅读 31
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int n,m;
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++)
{
scanf("%d",&a[i][j]);
}
}
for(int i = 0; i<= n; i++)
{
for(int j = 0; j<=i+1;j++)
{
f[i][j] = -INF;
}
}
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]);
//遍历最后一行,比较最大值
int res = -INF;
for(int i = 1; i<=n;i++) res = max(res,f[n][i]);
printf("%d\n",res);
return 0;
}
也可以倒序dp
,更简单些,因为倒序不需要考虑边界问题
如果是倒序的话,方向是从右向左,从上到下,首先i = n的时候, 最后一排会出现f[i][j] = a[i][j]
的情况,然后处理倒数第二行时,他是max(f[i+1][j],f[i+1][j+1])
对比的下方和右下方,即使是最右边的元素也不会处理到边界问题,所以可以不对f初始化为-INF,但是如果正序dp
的话,他选择的方式是max(f[i-1][j-1],f[i-1][j])
,是左上角和上方,这样的话最左边的元素会处理到边界,所以需要处理边界问题
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int f[N][N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>f[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=i;j>=1;j--){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
}
}
cout<<f[1][1]<<endl;
}