KirinRYato @ 2023-09-27 23:21:39
#include<bits/stdc++.h>
using namespace std;using namespace std;
const int N=1e3+5;
int n,a[N][N];
int nums(int num,int i,int j){
if(i>n) return num;
if(i==n) return num+a[i][j]+max(a[i+1][j+1],a[i+1][j]);
return max(nums(num+a[i][j],i+1,j),nums(num+a[i][j],i+1,j+1));
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
cout<<nums(0,1,1);
return 0;
}by Jianbing_Juan @ 2023-09-27 23:58:10
众所周知，dp的正确使用方式是用数组来转移状态。
用函数递归容易挂，容易超时（血的教训）
by KirinRYato @ 2023-09-29 13:21:28
@Jianbing_Juan 好的，谢谢
by heyx0201 @ 2023-10-01 20:50:25
@lingaohui @Jianbing_Juan 或许还有另一种方式：记忆化搜索
by Jianbing_Juan @ 2023-10-01 20:55:19
@heyx0201 你说得对，但是转移太容易挂了（可能是我太蒻了）
by heyx0201 @ 2023-10-01 20:56:18
@Jianbing_Juan
说实话我的记忆化也写不好（
by Soda_mew @ 2023-10-03 22:00:11
这道题正解肯定是dp辣
当然你可以试一试写记忆化
（肯定会T但T的少力）
by huangmingyi @ 2023-10-08 18:59:24
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int n,a[N][N];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=i;j++){
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
}
}
cout<<a[1][1];
return 0;
}