题目描述

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

动态规划
每个月的兔子数量为dp[i]
dp[i]=dp[i-1]+dp[i-2] 其中i>=3
兔子=上个月的+新出生
由于第三个月才能开始生育，新出生的兔子取决于两个月前兔子的数量

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int month;
    while(cin>>month){
        if(month==1||month==2)
            {cout<<1<<endl;continue;}
        vector<int> dp(month+1,0);
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=month;i++){
            dp[i]=dp[i-1]+dp[i-2];//i-1是上个月的，i-2的满足生育能力的（第三个月）
        }
        cout<<dp[month]<<endl;
    }
    //1 1 2 3 5 8 13 21 34
}