动态规划：

题目：

讲解+代码：

#include <bits/stdc++.h>
using namespace std;
long long n,a[1005][1005],dp[1005][1005];
int main(){cin>>n;for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j];for(int j=1;j<=n;j++) dp[n][j]=a[n][j];//最下一层直接赋值（初始化） for(int i=n-1;i>=1;i--){ //从下往上推，避免求完还要求最大值 for(int j=1;j<=i;j++){dp[i][j]=max(dp[i+1][j+1],dp[i+1][j])+a[i][j];//动态转移方程式 }}cout<<dp[1][1];return 0;
}