1 //（1）深搜
2 #include<iostream>
3 #include<cstdio>
4 #include<cstdlib>
5 using namespace std;
6 const int mmax=1001;
7 int a[mmax][mmax];
8 int n;
9 void dfs(int,int,int);
10 int ans;
11 int main()
12 {
13 scanf("%d",&n);
14 for(int i=1;i<=n;i++)
15 for(int j=1;j<=i;j++)
16 scanf("%d",&a[i][j]);
17 dfs(1,1,a[1][1]);//走到（1,1）目前的和为a[1][1]
18 cout<<ans;
19 return 0;
20 }
21 void dfs(int x,int y,int c)
22 {
23 if(x==n)//深搜到最后
24 {
25 if(c>ans)//如果目前的和比之前找的大
26 ans=c;//更新
27 return;
28 }
29 dfs(x+1,y,c+a[x+1][y]);//深搜左边
30 dfs(x+1,y+1,c+a[x+1][y+1]);//深搜右边
31 }
32 //（2）记忆化搜索（上一种方法超时的原因是因为对于同一个点重复递归了）
33 #include<iostream>
34 #include<cstdio>
35 #include<cstring>
36 using namespace std;
37 int n;
38 const int mmax=1001;
39 int a[mmax][mmax],f[mmax][mmax];//f[x][y]为（x,y）到金字塔底部的最大值
40 int dfs(int,int);
41 int main()
42 {
43 scanf("%d",&n);
44 memset(f,-1,sizeof(f));
45 for(int i=1;i<=n;i++)
46 for(int j=1;j<=i;j++)
47 scanf("%d",&a[i][j]);//输入
48 dfs(1,1);//从（1,1）深搜
49 cout<<f[1][1]<<endl;//输出（1,1）到底部的最大值
50 return 0;
51 }
52 int dfs(int x,int y)
53 {
54 if(f[x][y]==-1)//如果当前点没有递归过
55 {
56 if(x==n)f[x][y]=a[x][y];//如果已经到达底部，那么（x,y）到底部的和就是其本身
57 else
58 f[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));//否则（x,y）到底部的和就等于本身加上左下和右下中较大的一个
59 }
60 return f[x][y];//返回
61 }
62 //（3）额。。。就是算出从头到每个点的最大和，最后扫一遍最后一行找最大值就好
63 #include<iostream>
64 #include<cstdio>
65 using namespace std;
66 int n;
67 const int maxx=1001;
68 int a[maxx][maxx],f[maxx][maxx];
69 int main()
70 {
71 scanf("%d",&n);
72 for(int i=1;i<=n;i++)
73 for(int j=1;j<=i;j++)
74 scanf("%d",&a[i][j]);
75 f[1][1]=a[1][1];//从头到（1,1）的和就是（1,1）本身
76 for(int i=2;i<=n;i++)
77 {
78 for(int j=1;j<=i;j++)
79 {
80 f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];//等于其上左右较大的一个加上其本身；‘
81 }
82 }
83 int ans=0;
84 for(int i=1;i<=n;i++)
85 ans=max(ans,f[n][i]);//扫最后一行找最大值
86 cout<<ans;
87 return 0;
88 }