1004: [递归]母牛的故事（Java代码）

解题思路: 动态规划

注意事项:

参考代码:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		// 动态规划，存储每年的母牛数量
		int[] cowsNumber = new int[55]; // 题目中已知最大为54
		List<Integer> years = new ArrayList<>();
		// 录入数据
		while (true) {
			int year = scanner.nextInt();
			if (year == 0)
				break;
			years.add(year);
		}
		// 开始计算
		for (Integer year : years) {
			// 对于已经计算过的年母牛数量，可以输出后直接略过，不需要重复计算
			if (cowsNumber[year] > 0) {
				// 输出
				System.out.println(cowsNumber[year]);
				continue;
			}
			for (int j = 1; j <= year; j++) {
				// 前四年只有第一头母牛会生出小母牛
				if (j <= 4) {
					cowsNumber[j] = j;
				} else {
					// 前一年的数量 + 新出生的母牛数量（往前推三年的数量）
					cowsNumber[j] = cowsNumber[j - 1] + cowsNumber[j - 3];
				}
			}
			// 输出
			System.out.println(cowsNumber[year]);
		}

	}

}