许豪 @ 2017-04-23 07:18:24
#include<cstdio>
#include<iostream>
using namespace std;
int hang[2001][2001];
int tt[2001][2001]={0};
int n;
int dpp(int,int);
int maxx(int,int);
int main()
{
cin>>n;
for(int j=1;j<=n;j++)
{
for(int k=1;k<=j;k++)
{
cin>>hang[j][k];
}
}
dpp(1,1);
cout<<tt[1][1];
cin>>n;
return 0;
}
int dpp(int xx,int yy)
{
if(xx==n) return hang[xx][yy];
if(tt[xx][yy]!=0) return tt[xx][yy];
tt[xx][yy]=maxx(dpp(xx+1,yy)+hang[xx][yy],dpp(xx+1,yy+1)+hang[xx][yy]);
}
int maxx(int ss,int uu)
{
if(ss>uu) return ss;
else return uu;
}by Skyboys @ 2023-07-28 21:24:57
递归会TLE
要递推
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010;
int n,a[N][N],dp[N][N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)cin>>a[i][j];
for(int i=n;i>=1;i--)
for(int j=1;j<=i;j++)
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
cout<<dp[1][1]<<endl;
return 0;
}