#8TLE求助

lmy_2011 @ 2023-05-13 18:39:07

#include<cstdio>
#include<iostream>
using namespace std;
int n,a[1005][1005],dp[1005][1005];
int dfs(int x,int y)
{
    if(x==n) 
    {
        return dp[x][y]=a[x][y];
    }
    if(dp[x][y]>0) 
    {
        return dp[x][y];
    }
    return dp[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++) 
        {
            cin>>a[i][j];
        }
    }
    cout<<dfs(1,1);
    return 0;
}

by Lovely_CCCyh___ @ 2023-05-13 19:02:33

It is a dp.

by lmy_2011 @ 2023-05-13 20:46:17

@_FoolCYH 我用的是记忆化搜索……

by Lovely_CCCyh___ @ 2023-05-13 20:47:04

e

by lmy_2011 @ 2023-05-13 20:48:27

@_FoolCYH 当然谢谢你看到我这个帖子

by accounts_somebody @ 2023-05-14 09:56:15

@lmy_2011

在 int main() 后面加上：

memset(dp,-1,sizeof dp);

所有输入在 [0,100] 范围内。

有0的情况

by accounts_somebody @ 2023-05-14 10:00:25

再改成：

if(dp[x][y]>=0) 
{
    return dp[x][y];
}

就行了

by lmy_2011 @ 2023-05-14 20:49:54

@li_bai_Delete gzt，太谢谢你了