AcWing 898. 数字三角形
原题链接
简单
作者:
三个石头的蓝色背包
,
2022-02-25 14:44:48
,
所有人可见
,
阅读 243
自底向上,避免一些边界问题,空间优化简单,且最后的dp[0]即为所求
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int n;
int dp[N][N];
int arr[N][N];
int main(){
cin >> n;
for(int i=0; i<n; ++i){
for(int j=0; j<=i; ++j){
cin >> arr[i][j];
}
}
for(int i=n-1; i>=0; --i){
for(int j=0; j<=i; ++j){
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + arr[i][j];
}
}
cout << dp[0][0] << endl;
return 0;
}
优化为一维的dp,直接去除第一维即可,因为自底向上已经避免了重复计算的问题
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int n;
int dp[N];
int arr[N][N];
int main(){
cin >> n;
for(int i=0; i<n; ++i){
for(int j=0; j<=i; ++j){
cin >> arr[i][j];
}
}
for(int i=n-1; i>=0; --i){
for(int j=0; j<=i; ++j){
dp[j] = max(dp[j], dp[j+1]) + arr[i][j];
}
}
cout << dp[0] << endl;
return 0;
}