题目描述

blablabla

样例

blablabla

算法1

原地修改，用更少的空间

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int dp[N][N];
int main()
{
    int n;cin>>n;
    //这里由于没有初始化dp为负无穷，导致如果有负数就会选择不存在的0
    memset(dp,-0x3f,sizeof dp);
    cin>>dp[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>dp[i][j];
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+dp[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){ans=max(ans,dp[n][i]);}
     cout<<ans;
    return 0;
}