401 数字三角形 记忆化搜索

视频链接：https://www.bilibili.com/video/BV16V411U7Gc/

Luogu P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1005;
int n,a[N][N],f[N][N];

int dfs(int x,int y){
  if(f[x][y]!=-1) return f[x][y];   //记忆化搜索
  if(x==n) return f[x][y]=a[x][y];  //边界
  int mx=max(dfs(x+1,y),dfs(x+1,y+1));
  return f[x][y]=mx+a[x][y];
}
int main(){
  scanf("%d",&n);
  for(int i=1; i<=n; i++)
    for(int j=1; j<=i; j++)scanf("%d",&a[i][j]);
    
  memset(f,-1,sizeof f);
  dfs(1,1);
  printf("%d\n",f[1][1]);
}