1.题目介绍

有一对兔子，从出生后第 3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，求第n个月的兔子总对数为多少？

2.题解

2.1 动态规划

思路

类似于爬楼梯的思路。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算第n个月的兔子总共多少对。
     * @param count int整型 第多少个月后兔子总对数
     * @return long长整型
     */
    long long calculateTotal(int count) {
        if (count < 3) return 1;
        long long i = 1, j = 1, ans = i + j;
        for (int k = 1; k <= count - 3; k++){
            i = j;
            j = ans;
            ans = i + j;
        }
        return ans;
    }
};

2.2 递归

思路

原理采自于斐波拉契数列

代码

class Solution {
public:
    long long calculateTotal(int count) {
        if (count < 3) return 1;
        return calculateTotal(count - 1) + calculateTotal(count - 2);
    }
};