描述

题目描述

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

示例

知识点：递推，递归，动态规划

难度：⭐⭐⭐

题解

图解：

方法一：递推

解题思路：

利用动态规划的思想，通过规律进行递推，找出

算法流程：

分别用三个变量表示：一、二、三月龄兔子数量，addVal 保存下个月将繁殖的兔子数量
第二个月开始递推：
- 三月龄及以上兔子总数 = 二月龄兔子总数 + 原本三月龄及以上兔子总数
- 二月龄兔子总数 = 上个月的一月龄兔子总数
- 一月龄（即这个月出生）兔子总数 = 上个月将繁殖的兔子数量、
- 下个月将出生的兔子 = 下个月成为三月龄及以上的兔子数量
最后返回第 N 个月的总量即可

Java 版本代码如下：

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	System.out.println(solution(scanner.nextInt()));
        }

    }

    private static int solution(int month) {
    	// 第一个月初始化
    	// 一月龄兔子总数
    	int oneMonth = 1;
    	// 二月龄兔子总数
    	int twoMonth = 0;
    	// 三月龄及以上兔子总数
    	int threeMonth = 0;
    	// 下个月将繁殖的兔子数量
    	int addVal = 0;
    	// 第二个月开始递推, i表示第i个月
    	for(int i = 2; i <= month; i++) {
    		// 三月龄及以上兔子总数 = 二月龄兔子总数 + 原本三月龄及以上兔子总数
    		threeMonth += twoMonth;
    		// 二月龄兔子总数 = 上个月的一月龄兔子总数
    		twoMonth = oneMonth;
    		// 一月龄（即这个月出生）兔子总数 = 上个月将繁殖的兔子数量
    		oneMonth = addVal;
    		// 下个月将出生的兔子 = 下个月成为三月龄及以上的兔子数量
    		addVal = twoMonth + threeMonth;
    	}
    	return (oneMonth + twoMonth + threeMonth);
    }
}

复杂度分析：

时间复杂度： $O (N)$ ，N 为输入的月数，需要遍历 [2…N]

空间复杂度： $O (1)$ ，只用到了几个变量表示三个状态

方法二：递归

解题思路：

递归中可以通过备忘录减少重叠子问题

算法流程：

维护一个备忘录，用来保存计算过的状态，减少重叠子问题
明确定义递归函数：返回第n个月兔子总量
递归终止条件：n == 1 或 n == 2时，即第一和第二个月的兔子总数为1
如果备忘录已经保存了该月份的数据，表示已经计算过，直接返回即可，不需要再计算
根据规律以及函数定义，进行递归调用，同时保存状态到备忘录

Java 版本代码如下：

import java.util.*;
 
public class Main {
	// 备忘录，减少重叠子问题
    private static int[] memo;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
        	int month = scanner.nextInt();
        	// 备忘录里的元素都初始化为-1
			memo = new int[month + 1];
			Arrays.fill(memo, -1);            
        	System.out.println(dp(month));
        }

    }

  	// 返回第n个月兔子总量
    private static int dp(int n) {
    	// 递归终止条件
    	if(n <= 2) {
    		return 1;
    	}
    	// 使用备忘录
    	if(memo[n] != -1) {
    		return memo[n];
    	}
    	// 递归调用，满足规律
    	memo[n] = dp(n - 1) + dp(n - 2);
    	return memo[n];
    }
}

复杂度分析：

时间复杂度： $O (N)$ ，子问题经过备忘录优化后为 N 个子问题，子问题处理的时间复杂度为 O(1)，因此总的时间复杂度为 O(N)

空间复杂度： $O (N)$ ，递归所需要的栈的深度

题解 | #统计每个月兔子的总数#

描述

题解

方法一：递推

方法二：递归