19 换钱的方法数
Table of Contents

ac

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static int mod = 1_000_000_000 + 7;

    /**
     * 时间复杂度O(N*aim)
     * 空间复杂度O(aim)
     * @param args
     */
    public static void main(String[] args) {

        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[aim+1];
        for(int i=0;i<=aim;i++) {
            dp[0] = 0;
        }
        dp[0] = 1;
        for(int i=0;i<n;i++){
            int cur = arr[i];
            int[] dpTmp = new int[aim+1];
            // j 从 1 到 aim
            for(int j=1;j<=aim;j++){
                // 使用 cur 的张数0,1,2...
                // 剩下 j - cur * k
                for(int k=0;k<=j/cur;k++){
                    dpTmp[j] = (dpTmp[j] + dp[j - k * cur]) % mod;
                }
            }
            for(int j=1;j<=aim;j++){
                dp[j] = dpTmp[j];
            }
        }
        int rs = dp[aim] % mod;
        System.out.println(rs);
    }

}

4 15
5 10 25 1

初始状态

index\money 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1(5) 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2(10) 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3(25) 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15
4(1) 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static int mod = 1_000_000_000 + 7;

    /**
     * 时间复杂度O(N*aim)
     * 空间复杂度O(aim)
     * @param args
     */
    public static void main(String[] args) {

        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[][] dp = new int[n+1][aim+1];
        for(int i=0;i<=aim;i++) {
            dp[0][i] = 0;
        }
        for(int i=0;i<=n;i++){
            dp[i][0] = 1;
        }
        for(int i=0;i<n;i++){
            int cur = arr[i];
            // j 从 1 到 aim
            for(int j=1;j<=aim;j++){
                // 使用 cur 的张数0,1,2...
                // 剩下 j - cur * k
                for(int k=0;k<=j/cur;k++){
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j - k * cur]) % mod;
                }
            }
        }
        int rs = dp[n][aim] % mod;
        System.out.println(rs);
    }

}