题意：
        有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，
        假如兔子都不死，问第n个月的兔子总数为多少？

方法一：
动态规划

思路：
        该问题是斐波那契数列求解问题。
        公式：当前项等于前两项之和。
        直接循环计算。

     


#include <bits/stdc++.h>

using namespace std;
int dp[1000005];

int main(){

    dp[1]=1;//初始化
    dp[2]=1;
    for(int i=3;i<=1000000;i++)//动态规划打表
        dp[i]=dp[i-1]+dp[i-2];
    int x;
    while(cin >> x){//输入
        cout << dp[x] << endl;
    }
    return 0;
}


时间复杂度：
空间复杂度：


方法二：
记忆化递归

思路：
        
        递归并记忆化存储，优化了时间复杂度。

 
#include <bits/stdc++.h>

using namespace std;
int dp[1000005];

int f(int x){//递归
    if(x<=2)
        return 1;
    if(dp[x])
        return dp[x];
    return dp[x]=f(x-1)+f(x-2);//记忆化存储
}
int main(){

    int x;
    while(cin >> x){//输入
        cout << f(x) << endl;
    }
    return 0;
}



时间复杂度：
空间复杂度：