dfs写的，为什么只有20分，样例全过，两WA,六TLE

tjm20101204 @ 2022-10-29 20:36:22

#include <bits/stdc++.h>
using namespace std;
int num;
int n;
void dfs(int step)
{
    if(step>n)
    {
        return;
    }
    if(step == n)
    {
        num++;
        num=num%998244353;
    }
    for(int i=1; i<=3; i++)
    {
        dfs(step+i);
    }
}
int main()
{
    cin>>n;
    dfs(0);
    cout<<num;
    return 0;
}

by tjm20101204 @ 2022-10-29 20:37:17

求助大佬

by 阿宁已被领养 @ 2022-10-29 20:38:35

@tjm20101204

这应该用递推或者dp或者记忆化吧......

by tjm20101204 @ 2022-10-29 20:40:26

谢谢大佬，我试着写一下

by wangzihan622 @ 2022-10-29 20:44:21

n是5000，您这代码用深搜必超，而且您这怎么不用long long，深搜有一个外号：高级的枚举，在n>100时请您尽量不用深搜，除非您很会优化

by 阿宁已被领养 @ 2022-10-29 20:45:39

@wangzihan622 《神搜复杂度之加一车剪枝》

by int_stl @ 2022-12-21 19:08:28

当n=5000时，输出结果为6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626,所以要用高精度。