题目的主要信息：

• 一开始有一只兔子，每只兔子在第三个月会生一只兔子，假设每只兔子都不会死
• 题目要求计算第n个月的时候兔子的总数

方法一：动态规划

假设第n个月的兔子数量为num[n],第n个月会继承第n-1个月已有的兔子，同时，可能会有新出生的兔子。由题目可知，每只兔子在第三个月都会生一只兔子，所以第n个月出生的兔子数量等于第n-2月时的兔子数量，即num[n]=num[n-1]+num[n-2]。 具体做法：

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    while(cin>>n)
    {
        int num[n+1];//用于动态规划的数组
        num[0]=0;//第0个月0只兔子
        num[1]=1;//第1个月1只兔子
        num[2]=1;//第2个月兔子还没生兔子，仍只有一只兔子
        for(int i=3;i<=n;i++){
            num[i]=num[i-1]+num[i-2];//第i个月的兔子等于上个月的兔子数量加上新出生的兔子数量
        }
        cout<<num[n]<<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，动态规划需要遍历一遍。
• 空间复杂度：$O(n)O(n)$，动态规划数组大小为n。

方法二：变量迭代法

和动态规划思想一样，第n个月出生的兔子数量等于第n-2月时的兔子数量，即num[n]=num[n-1]+num[n-2]。但是不使用动态规划数组，减少空间复杂度，使用变量num_1和num_2，num_1代表前一个月的兔子数量，num_2代表前两个月的兔子数量，在循环过程中不断更新这两个变量。

具体做法：

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    while(cin>>n)
    {
        if(n<3){//没到第三个月不会生新的兔子
            cout<<"1"<<endl;
            continue;
        }
        int result=0;
        int num_1=1;//上一个月的兔子数量
        int num_2=1;//前2个月的兔子数量
        for(int i=3;i<=n;i++){
            result=num_1+num_2;//第i个月的兔子等于上个月的兔子数量加上新出生的兔子数量
            num_2=num_1;//更新
            num_1=result;
        }
        cout<<result<<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每次需要遍历一遍更新变量。
• 空间复杂度：$O(1)O(1)$，只使用了常数空间来存储迭代的变量。