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

使用动态规划解决，多多学习，知乎高赞思路：https://zhuanlan.zhihu.com/p/365698607

import java.util.Scanner;

public class Main {
     public static void main(String[] args) {
        /*
            高赞：https://zhuanlan.zhihu.com/p/365698607
            使用动态规划解决问题的方法，遵循以下步骤：
                1.穷举分析：从头开始分析问题，多列几组问题出来
                2.确定边界：那些是不能在规律中解决的，如 f(1) = 1，f(2) = 1
                3.找出规律，确定最优子结构：如 f(5) = f(3) + f(4)
                4.写出状态转移方程：f(n) = f(n - 2) + f(n - 1)
            1月：不能生
                f(1) = 1
            2月：不能生
                f(2) = 1
            3月：可以生一只，加上原来的，有 2 只兔子
                       [3月生]
                f(3) = (1 + 1)
            4月：1月和2月的兔子，还可以生，但是3月刚出生的不行，新生用括号和妈妈括了起来 ~
                       [4月生]   [3月的小兔子]
                f(4) = (1 + 1) + 1
            5月：1月2月的兔子还在生，3月生的兔子也能生了，但是4月的还不行
                       [5月生]   [3月兔生]  [还不能生的小兔子]
                f(5) = (1 + 1) + (1 + 1) + 1
            公式代换以下
                f(5) = f(3) + f(4)
            再变为
                f(n) = f(n - 2) + f(n - 1)
            边界为 
                f(1) 和 f(2)
         */
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();

        // 定义一个数组用来存储之前月的兔子数 ~  
        int[] arr = new int[num];
        // 边界设定：第一个月
        arr[0] = 1;
        // 边界设定：第二个月
        arr[1] = 1;
	    // 迭代处理后续的月份
        for(int i = 2; i < num; i++) {
            // 例如第三个月：arr[3] = arr[2 - 2] + arr[2 - 1]
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        System.out.println(arr[num - 1]);
    }
}