先上代码

#include<bits/stdc++.h>
//#include<iostream>
using namespace std;
int n,tree[1005][1005],book[1005][1005];
int maxx(int a,int b){
	if(a>b) return a;
	return b;
}
int dfs(int x,int y){
	if(x>n){
		return 0;
	}
	if(book[x][y]!=0){
		return book[x][y];
	}else{
		return book[x][y]=maxx(dfs(x+1,y),dfs(x+1,y+1))+tree[x][y];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			scanf("%d",&tree[i][j]);
		}
	}
	printf("%d",dfs(1,1));
	return 0;
}

本蒟蒻还没学DP，求大佬们看看这dfs还有可以优化的地方吗~