Deric456 @ 2024-08-16 09:16:12
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define maxN 1005
int a[maxN][maxN],N,ans=0;
void Dfs(int x,int y,int CurrentValue){
//终止条件
if(x==N-1){
if(CurrentValue>ans){
ans=CurrentValue;
}
return;
}
Dfs(x+1,y,CurrentValue+a[x+1][y]);
Dfs(x+1,y+1,CurrentValue+a[x+1][y+1]);
}
int main(){
cin>>N;
for(int i=0;i<N;i++)
for(int j=0;j<=i;j++)
cin>>a[i][j];
Dfs(0,0,a[0][0]);
cout<<ans<<endl;
return 0;
}
by dmc0702 @ 2024-08-16 09:19:33
@Deric456 这道题要动态规划,普通搜索肯定超时
by dmc0702 @ 2024-08-16 09:22:28
记忆化搜索应该也行
by Deric456 @ 2024-08-16 09:39:11
@dmc0702 谢谢!AC了