题目的主要信息：

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

我们有如下计算：

我们发现除了最前面两个月，其余月份的兔子数都是有它前面的两个月相加而来，因此我们有如下结论：$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);

int main() {

	int n;
	cin >> n;
    
	cout << getSum(n) << endl; //输出结果

	return 0;
}

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

复杂度分析：

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

方法二：迭代

具体做法：

除了自上而下的递归，我们还可以利用像上述数组一样的自下而上的相加，反正除了第一二月外，我这个月的值等于它前两个月的值相加，我们可以从第三个月开始不断累加，并更新前两个月的值即可。

#include <iostream>
using namespace std;

int getSum(int n);

int main() {

	int n;
	cin >> n;
    
	cout << getSum(n) << endl; //输出结果

	return 0;
}

int getSum(int n) {
    if(n <= 2) //2及以下直接返回
        return 1;
    int a = 1; //表示当前要计算的月份前一个月
    int b = 1; //表示当前要计算月份的前两个月
    int res = 0; 
    for(int i = 3; i <= n; i++){ //遍历3-n
        res = a + b; //直接相加
        b = a; //更新前两个
        a = res; //
    }
    return res;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历
• 空间复杂度：$O(1)O(1)$，常数个变量，无额外空间