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

2、本题有多组数据。

方法一：归纳总结

所有兔子就三种,每个月更新三种的数量：

迭代完全部相加即为所有兔子数量count；

第三个月及以上，可生育big；

第二个月，不可生育little；

第一个月，小萌新little。

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();//输入数据
            int count = 0;
            int rabbitLittle = 1;//一月新生兔子
            int rabbitBig = 0;//二月大或者更多月份的兔子
            for (int j = 0; j < n; j++) {
                count = rabbitLittle + rabbitBig;//本月兔子数量=一月新生兔子+二月大兔子
                rabbitLittle = rabbitBig;//下个月，每个二月大兔子将会生产 一个 一月新生兔。
                rabbitBig = count; //下个月所有二月大兔子将会满足 两个月大兔子的 条件。
            }
            System.out.println(count);
        }
    }

方法二：斐波那契数列

具体方法

我们可以先来推导一个

第一个月 只有一对

第二个月 只有一对

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

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

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

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

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

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

方法三：动态规划

具体做法

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

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)O(n)O(n)，动态规划数组大小为n。