题解 | #拼凑面额#

import java.util.Scanner;

public class Main {
    private static final int[] values = {1,5,10,20,50,100};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            solution1(in);
            // solution2(in);
        }
    }

    /**
     * 动态规划
     *
     * dp[i]表示拼成面额i的组合个数
     * dp[i] = dp[i-1] + dp[i-5] + dp[i-10] + dp[i-20] + dp[i-50] + dp[i-100]
     *
     * @param in
     */
    private static void solution1(Scanner in){
        int money = in.nextInt();
        long[] dp = new long[money+1];
        dp[0] = 1L;

        for(int i=0; i<values.length; i++){
            for(int j=1; j<=money; j++){
                if(j >= values[i]){
                    dp[j] += dp[j-values[i]];
                }
            }
        }

        System.out.println(dp[money]);
    }


    /**
     * 动态规划
     *
     * dp[i][j]表示前i种面额拼成j的组合个数
     * dp[i][j] += dp[i-1][j-k*values[i]], while j-k*values[i] >= 0
     *
     * @param in
     */
    public static void solution2(Scanner in){
        int money = in.nextInt();
        long[][] dp = new long[values.length][money+1];

        // init
        for(int i=0; i<values.length; i++){
            dp[i][0] = 1;
        }
        for(int j=1; j<=money; j++){
            dp[0][j] = 1;
        }
        
        for(int i=1; i<values.length; i++){
            for(int j=1; j<=money; j++){
                int k = 0;
                while(j-k*values[i] >= 0){
                    dp[i][j] += dp[i-1][j-k*values[i]];
                    k++;
                }
            }
        }
        
        System.out.println(dp[values.length-1][money]);
    }
}