402 数字三角形 线性DP

视频链接：

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

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

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

int main(){
  scanf("%d",&n);
  for(int i=1; i<=n; i++)
    for(int j=1; j<=i; j++)
      scanf("%d",&f[i][j]);
    
  for(int i=n; i>=1; i--)
    for(int j=1; j<=i; j++)
      f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
    
  printf("%d\n",f[1][1]);
}