题目的主要信息:

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

我们有如下计算:

月份 兔子数(对)
第1个月 1对兔子
第2个月 1对兔子
第3个月 2对兔子(第一对生出第二对)
第4个月 3对兔子(第一对生出第三对)
第5个月 5对兔子(第一对生出第四对、第二对生出第五对)
第6个月 8对兔子(第一对生出第六对、第二对生出第七对、第三对生出第八对)

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

方法一:递归

具体做法:

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

alt

#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(2n)O(2^n),如图所示,树型递归,遍历每个结点
  • 空间复杂度:O(n)O(n),递归栈最大深度为nn

方法二:动态规划

具体做法:

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

方法三:迭代

具体做法:

注意到方法二动态规划每次循环只使用到了第i1i-1个变量和第i2i-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),常数级空间