/*
  DP的基础问题，题目稍有错误，但不影响做题。
  DP基本思想：划分子问题确定状态与状态之间的转移关系，使用递推或记忆化搜索等方法解决问题
  题目中说可以走向相邻的点，实际是可以走向下面的点和下面的右边的点。 
*/ 
#include<iostream>
using namespace std;
int x[12][12],dp[12][12];
/*
	x[i][j]代表数塔中第i层第j个位置上的元素
	dp[i][j]代表从第i层第i层第j个位置上走到底层的数字最大之和 
*/
int main()
{
	int a;
	cin>>a;
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>x[i][j];//输入
			dp[i][j]=x[i][j];//初始化dp数组 
		}
	}
	for(int i=a-1;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=x[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
			/*
				动态转移方程：dp[i][j]=x[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
				                                         ↑          ↑   
				                                     下面的点	下面的右边的点 
			*/
		}
	}
	cout<<dp[1][1];//从顶层走到底层的最大值 
}

用DP递推

/*
int      %o/%lo 8 %d/%i/%ld/%li 10 %x/%lx 16
longlong %lld
float    %f/%e
double   %lf/%le
char     %c
char[]   %s
'a'=97
'z'=122
'A'=65
'Z'=90
'0'=48
'9'=57
*/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <limits>
#include <assert.h>
#include <stdlib.h>
#pragma GCC optimize(3) //O3
//#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//IOS
using namespace std;
#define LL long long
#define ull unsigned long long
const int N=10+10;
const int INF=0x3f3f3f3f;
const double pi=3.1416;
int n;
int a[N][N],f[N][N],ans;
int main(){
	//IOS;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
			f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(f[n][i],ans);
	}
	cout<<ans<<endl;
return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main(){

int a[11][11]={0},i,j,n,ans=0;

cin>>n;

for(i=1;i<=n;i++){

	for(j=1;j<=i;j++){

		cin>>a[i][j];

	}

}

for(i=2;i<=n;i++){

	for(j=1;j<=i;j++){

		a[i][j]=max(a[i-1][j],a[i-1][j-1])+a[i][j];

	} 

}

for(int i=1;i<=n;i++){

	ans=max(ans,a[n][i]);

}

cout<<ans;

return 0;

}