递归的记忆性，防止出现TLE

Question

这是一道洛谷的题目，题面是如下：

我采用的是递归算法，在数据较小的情况是没问题的。以下是无记忆性代码：

#include <bits/stdc++.h>
using namespace std;

int cnt=0;

int main()
{
    int n;
    cin>>n;
    void whatever(int n);
    whatever(n);
    cout<<cnt;
}

void whatever(int n)
{
    cnt++;
    if(n==1)    return;
    for(int i=1;i<=n/2;i++) whatever(i);
}

//---------------------------------------------------------

以上代码会出现超时的问题（因为递归的重复运算），而以下代码则是出现如上图的数值突然爆了的情况，求解。

//---------------------------------------------------------

#include <bits/stdc++.h>
using namespace std;

bool mark[105];
long int sto[105];
int whatever(int n)
{
    if(n==0)  {mark[0]=1; sto[0]=0; return 0;}
    if(mark[n]==false)   //haven't traveled it
    {
         mark[n]=true;      //marking it to be traveled one
         sto[n]=1;
    }
    else return sto[n];
    if (n==1) return 1;
    for(int i=0;i<=n/2;i++)
    {
        if(mark[i]==false)
        {
            sto[n]+=whatever(i);
            cout<<"sto["<<i<<"] is: "<<sto[i]<<"    whatever("<<i<<") is: " <<whatever(i)<<endl;
        }
        else
        {
            sto[n]+= sto[i];
        }

    }
    return sto[n];
}


int main()
{
    int n;
    long int sum;
    cin>>n;
    sum=whatever(n);
    cout<<n<<"对应是： "<<sum;
}

Answer 1

https://blog.csdn.net/qq_39445165/article/details/84191097