AKSZ-递推递归

刘骏霖

2024-04-14 17:06:18

发布于：香港

6阅读

0回复

0点赞

递归

递归要素

1、递归边界
2、递归方程

系统栈

一般可以存 $10^5$ 个int
不要再递归中创建数组

计划搜索

#include<bits/stdc++.h>
using namespace std;
long long dp[1005];//记忆化数组
long long f(long long n){
    if(n<=2){
        return 1;
    }
    if(dp[n]!=-1)return dp[n];//n的答案已经被计算过，剪枝
    return dp[n]=f(n-2)+f(n-1);//F(n-2)
}
int main(){
    int n;
    memset(dp,-1,sizeof(dp));//把数组全变成-1
    cin>>n;
    cout<<f(n);
}