题目的主要信息：

• 有一对兔子，从出生后第 3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第n个月的兔子对数为多少?

我们有如下计算：

我们发现除了最前面两个月，其余月份的兔子数都是有它前面的两个月相加而来，因此我们有如下结论：$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$，这正是大名鼎鼎的斐波那契数列。

方法一：递归

具体做法：

对于$f(n)=f(n-1)+f(n-2)f(n)=f(n-1)+f(n-2)$的问题，我们可以每次递归地寻找子问题，然后子问题累得到结果，子问题找到1或者2就停止。

#include<iostream>
using namespace std;

int getSum(int n) { //求每个月兔子数
    if(n == 1 || n == 2) //n=1或2跳出递归
        return 1;
    return getSum(n - 1) + getSum(n - 2); //返回前两个月相加
}

int main(){
    int n;
    while(cin >> n){ //每次输入n
        cout << getSum(n) << endl; 
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，如图所示，树型递归，遍历每个结点
• 空间复杂度：$O(n)O(n)$，递归栈最大深度为$nn$

方法二：动态规划

具体做法：

除了自上而下的递归，我们还可以利用像上述数组一样的自下而上的相加，反正除了第一二月外，我这个月的值等于它前两个月的值相加，第一二个月都初始化为1，从第三个月开始不断由前两个月累加，直到第$nn$个月。转移方程就是：$dp[i]=dp[i-1]+dp[i-2]dp[i]\; =\; dp[i\; -\; 1]\; +\; dp[i\; -\; 2]$

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    while(cin >> n){ //每次输入n
        vector<int> dp(n + 1);
        dp[1] = 1; //初始第一个月
        dp[2] = 1; //第二个月
        for(int i = 3; i <= n; i++) //后面的每个月由前面的累加
            dp[i] = dp[i - 1] + dp[i - 2];
        cout << dp[n] << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历dp数组一次
• 空间复杂度：$O(n)O(n)$，动态规划辅助数组dp的长度为$nn$

方法三：迭代

具体做法：

注意到方法二动态规划每次循环只使用到了第$i-1i-1$个变量和第$i-2i-2$个变量，那我们可以用两个变量不断滚动来优化。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){ //每次输入n
        if(n <= 2) //前两个月直接输出
            cout << 1 << endl;
        else{
            int dpi_2 = 1; //初始化第1个月
            int dpi_1 = 1; //初始化第2个月
            int output = 0;
            for(int i = 3; i <= n; i++){
                output = dpi_1 + dpi_2; //公式相加
                dpi_2 = dpi_1; //变量更新
                dpi_1 = output;
            }
            cout << output << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历到$nn$
• 空间复杂度：$O(1)O(1)$，常数级空间