动规基础题

#include<bits/stdc++.h>
using namespace std;
int a[150][150]={0};
int dp[150][150]={0};
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      cin>>a[i][j];
    }
  }
  dp[1][1]=a[1][1];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      dp[i+1][j]=max(dp[i][j],dp[i][j-1])+a[i+1][j];
      dp[i+1][j+1]=max(dp[i][j+1],dp[i][j])+a[i+1][j+1];
    }
  }
  int result=0;
  for(int i=1;i<=n;i++){
  	result=max(result,dp[n][i]);
  }
  cout<<result;
  return 0;
}