动态规划练习——从暴力递归—＞记忆化搜索—＞经典动态规划

题目

给定一个数组arr，全是正数且没有重复值，数组元素是人民币面值大小，可以重复取值。常量aim==1000元，要求从数组中取元素使得面值加起来为1000，求有多少种方式？

package com.harrison.class13;

public class Code06_CoinsWay {
    public static int ways1(int[] arr,int aim) {
        if(arr==null || arr.length==0 || aim<0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }
    
    // arr[index...]所有的面值都可以自由使用任意张
    // 组成rest有多少种方法
    public static int process1(int[] arr,int index,int rest) {
//        if(rest<0) {
//            return 0;
//        }
        // rest>=0
        if(index==arr.length) {// 当前位置来到了最后一张货币，没有货币可以选择了
            return rest==0?1:0;
        }
        // 当前有货币 arr[index]
        int ways=0;
        for(int zhang=0; zhang*arr[index]<=rest; zhang++) {
            ways+=process1(arr, index+1, rest-(zhang*arr[index]));
        }
        return ways;
    }
    
    public static int ways2(int[] arr,int aim) {
        if(arr==null || arr.length==0 || aim<0) {
            return 0;
        }
        int[][] dp=new int[arr.length+1][aim+1];
        // 一开始所有的过程都没有计算 dp[..][..]=-1
        for(int i=0; i<dp.length; i++) {
            for(int j=0; j<dp[0].length; j++) {
                dp[i][j]=-1;
            }
        }
        return process2(arr, 0, aim,dp);
    }
    
    // 如果index和rest的参数组合是没有算过的，dp[index][rest] == -1
    // 如果index和rest的参数组合是算过的，dp[index][rest] > -1
    public static int process2(int[] arr,int index,int rest,int[][] dp) {
        if(dp[index][rest]!=-1) {
            return dp[index][rest];
        }
        if(index==arr.length) {
            dp[index][rest]=rest==0?1:0;
            return dp[index][rest];
        }
        int ways=0;
        for(int zhang=0; zhang*arr[index]<=rest; zhang++) {
            ways+=process2(arr, index+1, rest-(zhang*arr[index]),dp);
        }
        dp[index][rest]=ways;
        return ways;
    }
    
    public static int ways3(int[] arr,int aim) {
        if(arr==null || arr.length==0 || aim<0) {
            return 0;
        }
        int N=arr.length;
        int[][] dp=new int[N+1][aim+1];
        dp[N][0]=1;// dp[N]][1...aim]=0;
        // 第N行已经填好了，从第N-1行开始填
        for(int index=N-1; index>=0; index--) {
            for(int rest=0; rest<=aim; rest++) {
                int ways=0;
                for(int zhang=0; zhang*arr[index]<=rest; zhang++) {
                    ways+=dp[index+1][rest-(zhang*arr[index])];
                }
                dp[index][rest]=ways;
            }
        }
        return dp[0][aim];
    }
    
    public static int ways4(int[] arr,int aim) {
        if(arr==null || arr.length==0 || aim<0) {
            return 0;
        }
        int N=arr.length;
        int[][] dp=new int[N+1][aim+1];
        dp[N][0]=1;
        for(int index=N-1; index>=0; index--) {
            for(int rest=0; rest<=aim; rest++) {
                dp[index][rest]=dp[index+1][rest];
                if(rest-arr[index]>=0) {
                    dp[index][rest]+=dp[index][rest-arr[index]];
                }
            }
        }
        return dp[0][aim];
    }
    
    public static void main(String[] args) {
        int[] arr= {5,10,50,100};
        int sum=1000;
        System.out.println(ways1(arr, sum));
        System.out.println(ways2(arr, sum));
        System.out.println(ways3(arr, sum));
        System.out.println(ways4(arr, sum));
    }
}