题目主要信息

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

2、本题有多组数据。

方法一：斐波那契数列

具体方法

我们可以先来推导一个

第一个月 只有一对

第二个月 只有一对

第三个月 原先的一对生出一对 共2对

第四个月 最开始的一对又生出一对 共3对

第五个月 第一对生一对，第二队到第三月 生一对，共5对

第六个月 第一对生一对，第二对生一对，第三对生一对，共8对

可以发现f(n) = f(n-1)+f(n-2)

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            System.out.println(f(n));
        }
    }
    public static int f(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        return  f(n-1)+f(n-2);
    }
}

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，如图所示，树型递归，遍历每个结点
• 空间复杂度：$O(n)O(n)$，递归栈最大深度为n

方法二：动态规划

具体做法

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

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            System.out.println(dp(n));
        }
    }
    public static int dp(int n){
        int num[] = new int[n+1];
        num[1] = 1;
        num[2] = 1;
        for(int i=3;i<=n;i++){
            num[i] = num[i-1] + num[i-2];
        }
        return  num[n];
    }
}

复杂度分析

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