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

import java.util.*;

// 这个java怎么没有初始化代码了，是我bug了吗
// 这题典型的动态规划，将所有月份的个数存入数组，找到状态迁移规律
// 这一题 ans[i] = ans[i - 2] * 2 + ans[i - 1] - ans[i - 2]
// 第i - 2的兔子一定成熟， i - 1与i - 2之差不成熟
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int month = in.nextInt();
            int[] ans = new int[month + 1];
            ans[1] = 1;
            ans[2] = 1;
            for (int i = 3; i < month + 1; i++) {
                ans[i] = ans[i - 2] * 2 + ans[i - 1] - ans[i - 2];
            }
            System.out.println(ans[month]);
        }
    }
}