母牛的故事_题解 三种解法，递归；记忆型递归；动态规划

解题思路:

        第n年的母牛的来源分别来自于前一年剩下的和往前推3年的母牛（能生的母牛，最早的也算在里面）

        6 = 前一年剩下的4头牛+（第2年新产的母牛刚具有生育能力生下的1头+最早的母牛1头）

        解题公式：f(n) = f(n-1) + f(n-3)

注意事项:

解法1 递归

import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            System.out.println(f(n));
        }
        
    }
    
    public static int f(int n){
        //前四天没有母牛出生
        if(n<=4){
            return n;
        }
        //上一天出生数加前三天的出生数
        return f(n-1)+f(n-3);
    }
    
}

解法2 记忆型递归+剪枝  避免计算重复子问题

import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            System.out.println(f(n));
        }
        
    }
    
    public static Integer[] arr = new Integer[999];
    
    public static int f(int n){ 
        //前四天没有母牛出生       
        if(n<=4){
            arr[n]=n;
            return n;
        }
        //剪枝避免计算重复子问题
        if(arr[n]!=null){
            return arr[n];
        }
        //记住存储结果 以便复用
        arr[n]=f(n-1)+f(n-3);        
        return arr[n];
    }
}

解法3 动态规划

import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int [] arr = new int[999];
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            for(int i = 1;i <= n;i++ ){
                //前四天没有母牛出生    
                if(i<=4){
                    arr[i]=i;
                }else{
                    arr[i]=arr[i-1]+arr[i-3];
                }
            }
            System.out.println(arr[n]);
        }
        
    }
    
}