记忆化递归题解

$$\begin{gathered} \textbf{我一眼就看出来了}\\ \hspace{15em}\textbf{——拉马努金} \end{gathered}$$

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int dfs(int f){
    if(f==1)
        return 1;
    else if(f==2)
        return 2;
    else if(f==3)
        return 4;
    if(a[f])return a[f];
    a[f]=dfs(f-1)+dfs(f-2)+dfs(f-3);
    return a[f];
}
int main(){
    int n;
    cin>>n;
    cout<<dfs(n);
    return 0;
}