题目链接：点击打开链接
这题和白皮的数字三角形是一样的。有很多题都是这个的变形比如1176
递归：
#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1e2+10; int a[maxn][maxn],d[maxn][maxn],n; int dp(int i,int j) { if(d[i][j]>0)return d[i][j]; return d[i][j]=a[i][j]+(i==n?0:max(dp(i+1,j),dp(i+1,j+1))); } int main() { int t,i,j; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=i;j++) scanf("%d",&a[i][j]); memset(d,-1,sizeof(d)); printf("%d\n",dp(1,1)); } return 0; }递推： #include <iostream> #include <stdio.h> #include<cstring> using namespace std; const int maxn=1e2+10; int a[maxn][maxn],flag[maxn],b[maxn][maxn]; int main() { int t,n,i,j; while(cin>>t) { while(t--) { cin>>n; memset(b,0,sizeof(b)); memset(a,0,sizeof(a)); for(i=1; i<=n; i++) for(j=1; j<=i; j++) cin>>a[i][j]; for(i=1; i<=n; i++) for(j=1; j<=i; j++) b[i][j]=max(b[i-1][j],b[i-1][j-1])+a[i][j]; int Max=0; for(i=1; i<=n; i++) if(Max<b[n][i])Max=b[n][i]; cout<<Max<<endl; } } return 0; }