AcWing 898. 数字三角形 dfs + 记忆化搜索
原题链接
简单
作者:
轻微做题
,
2021-02-06 20:46:38
,
所有人可见
,
阅读 314
dfs+记忆化搜索
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 5100;
int n;
int a[N][N];
int ans[N][N];
int dfs(int i, int j){
if(i == n) return a[n][j];
if(ans[i][j]) return ans[i][j];
ans[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + a[i][j];
return ans[i][j];
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= i; j ++){
cin >> a[i][j];
}
}
cout << dfs(1, 1) << endl;
return 0;
}
### 喜羊羊你可真nb