题意整理。

• 起初给定一对兔子，兔子第3个月会生一对兔子，并且此后每个月都会生一对，生出来的兔子也是这个样子。
• 假如兔子都不死，求第n个月的兔子对数。

方法一（迭代）

1.解题思路

这个题本质上是一个递归的问题。假设f(n)表示第n个月的兔子对数。第三个月才会生兔子，所以n为1和2时，均只有一对兔子。当n大于等于3时，第n个月的兔子对数为第n-1个月的兔子对数加上第n-1个月到第n个月之间新增的兔子，而只有相差至少2个月才会新增兔子，所以新增的兔子数为第n-2个月时的兔子对数，于是有f(n)=f(n-1)+f(n-2)。由于递归会产生大量重复的计算，我们可以用迭代来实现。

• 定义变量a、b、sum。a记录f(n-2)的兔子对数，b记录f(n-1)的兔子对数，sum记录f(n)的兔子对数。
• 使用循环来模拟时间的变化，将前两个月对应兔子对数之和赋值给当前sum，然后a变为b，b变为sum，表示过了一个月之后，对应兔子数的情况。

图解展示：

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) {
    //第三个月才会生兔子，所以n为1和2时，均只有一对兔子
    if(n==1||n==2) return 1;
    /*当n大于等于3时，第n个月的兔子对数为第n-1个月的兔子对数加上第n-1个月到第n个月
    之间新增的兔子，而只有相差至少2个月才会新增兔子，所以新增的兔子数为第n-2个月时
    的兔子对数，于是有f(n)=f(n-1)+f(n-2)。f(n)表示第n个月的兔子对数。
    */
    //a记录f(n-2)的兔子对数
    int a=1;
    //b记录f(n-1)的兔子对数
    int b=1;
    //sum记录f(n)的兔子对数
    int sum=0;
    for(int i=3;i<=n;i++){
        //相当于f(n)=f(n-1)+f(n-2)
        sum=a+b;
        //每过一个月a变为b,b变为sum
        a=b;
        b=sum;
    }    
    return sum;
}

3.复杂度分析

• 时间复杂度：需要进行$n-2n-2$次循环，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。