母牛的故事

public class Solution {
    // dp 定义: dp[i] 表示第i年有多少头牛
    // 初始化: dp[1] = dp[2] = dp[3] = dp[4] = 1;
    // 递推式: dp[i] = dp[i-1] + dp[i-3] (当前的牛数量 = 去年的牛数量 + 可以生小牛的牛数量)
    // 前三年的牛有 dp[i-3],这些牛包括了成熟的母牛(每年生一头),也包括了未成熟的小牛（它们在第四年可以生一头牛）
    // 所以把这两部分累加起来，也就是这dp[i-3]头牛可以在第i年生 dp[i-3]头
    // 可以结合这个例子理解一下: F(5) = F(4) + F(2)；画个图好理解一点
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] dp = new int[60];
        dp[1] = dp[2] = dp[3] = dp[4] = 1;

        for (int i = 5; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }

        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            System.out.println(dp[a]);
        }
    }
}

import java.util.Scanner;

/**
 * 有一头母牛，它每年年初生一头小母牛。
 * 每头小母牛从第四个年头开始，
 * 每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
 */
public class Muniu {

    public static int f1(int n) {
        if (n == 0){
            return 0;
        }
        int[] a = new int[n+1];
        if (n == 1){
            return 1;
        }else if (n == 2){
            return 2;
        }else if (n == 3){
            return 3;
        }else {
            a[1] = 1;
            a[2] = 2;
            a[3] = 3;
            for (int i = 4;i <= n; i++) {
                a[i] = a[i-1] + a[i-3];
            }
            return a[n];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            System.out.println(f1(n));
        }
        sc.close();
    }

    /**复杂度过高
    public static int f(int n) {
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else if (n == 3){
            return 3;
        }else {
            return f(n-1) + f(n-3);
        }
    }
     **/
}