一道 dp 的入门题。
\(O(2^n)\)：
考虑直接爆搜，可以考虑到所有情况。
\(O(n^2)\)：
考虑 \(dp\)，设 \(dp_{i,j}\) 代表到达第 \(i\) 层第 \(j\) 个数所能达到的最大值。
状态转移方程为 \(dp_{i,j}=a_{i,j}+\max(dp_{i-1,j-1},dp_{i-1,j})\)。
最终答案就是 \(\max(dp_{n,1},dp_{n,2},\dots,dp_{n,n})\)。
参考代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,ans,dp[1010][1010];
#define QwQ return 0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>dp[i][j];
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i][j]+=max(dp[i-1][j],dp[i-1][j-1]);
for(int i=1;i<=n;i++)
ans=max(ans,dp[n][i]);
cout<<ans;
QwQ;
}