换钱的方法数

话不多说上代码。解释书上有。
import java.util.Scanner;

public class Main{
public static final int mod = 1_000_000_007;

public static int coins1(int[] arr, int aim){
    if(arr.length == 0 || arr == null || aim < 0){
        return 0;
    }
    int[][] map = new int[arr.length+1][aim+1];
    return process1(arr, 0, aim, map);  
}
//暴力递归的方法
public static int process(int[] arr, int index, int aim){
    int res = 0;
    //base case
    if(index == arr.length){
          res = aim == 0 ? 1 : 0;
    }else{
             for(int k = 0; k * arr[index] <= aim; k ++){
                res += process(arr, index+1, aim - k * arr[index]);
              }
          }
    return res;
}
//记忆搜索的方法
public static int process1(int[] arr, int index, int aim, int[][] map){
    int res = 0;
    //base case
    if(index == arr.length){
          res = aim == 0 ? 1 : 0;
    }else{   
             int mapValue = 0;
             for(int k = 0; k * arr[index] <= aim; k ++){
                 mapValue = map[index+1][aim - k * arr[index]];
                 if(mapValue != 0){
                     res += mapValue == -1 ? 0 : mapValue;
                 }else{
                     res += process(arr, index+1, aim - k * arr[index]);
                 }
              }
          }
    map[index][aim] = res == 0 ? -1 : res; 
    return res;
}
//暴力递归——动态规划
public static int coins3(int[] arr, int aim){
    if(arr.length == 0 || arr == null || aim < 0){
        return 0;
    }
    //dp[i][j]:钱arr[0...i],目标j 有多少做法
    int[][] dp = new int[arr.length][aim+1];
    //base case
    for(int i = 0; i < arr.length; i++){
        dp[i][0] = 1;
    }
    for(int j = 1; arr[0] * j <= aim; j++){
        dp[0][arr[0] * j] = 1;
    }
    int num = 0;
    //遍历dp数组
    for(int i = 1; i < arr.length; i++){
        for(int j = 1; j <= aim; j ++){
            num = 0;
            //如何求dp[i][j]?
            for(int k = 0; j - k*arr[i] >= 0 ; k++){
                num = (num + dp[i-1][j - k*arr[i]]) % mod;
            }
            dp[i][j] = num;        
        }
    }
    return dp[arr.length-1][aim];
}
//动态规划O(N aim)
public static int coins4(int[] arr, int aim){
    if(arr.length == 0 || arr == null || aim < 0){
        return 0;
    }
    //dp[i][j]:钱arr[0...i],目标j 有多少做法
    int[][] dp = new int[arr.length][aim+1];
    //base case
    for(int i = 0; i < arr.length; i++){
        dp[i][0] = 1;
    }
    for(int j = 1; arr[0] * j <= aim; j++){
        dp[0][arr[0] * j] = 1;
    }
    //遍历dp数组
    for(int i = 1; i < arr.length; i++){
        for(int j = 1; j <= aim; j ++){
            dp[i][j] = dp[i-1][j] % mod;
            dp[i][j] = (dp[i][j] +  (j - arr[i] >= 0 ? dp[i][j-arr[i]] : 0) )% mod;
        }
    }
    return dp[arr.length-1][aim];
}
//本题的最优解 时间O(N aim) 空间O(aim)
 public static int coins5(int[] arr, int aim){
    if(arr.length == 0 || arr == null || aim < 0){
        return 0;
    }
    //dp[i][j]:钱arr[0...i],目标j 有多少做法
    int[] dp = new int[aim+1];
    //dp[0] = 1;
    for(int j = 0; arr[0] * j <= aim; j++){
        dp[arr[0] * j] = 1;
    }
    //遍历dp数组
    for(int i = 1; i < arr.length; i++){
        for(int j = 1; j <= aim; j ++){
            dp[j] = dp[j] % mod;
            dp[j] = (dp[j] +  (j - arr[i] >= 0 ? dp[j-arr[i]] : 0) )% mod;
        }
    }
    return dp[aim];
}   
public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int aim = sc.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
        arr[i] = sc.nextInt();
    }
    System.out.println(coins5(arr, aim));
}

}