Java的动态规划

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class BookBuying {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 读取输入的钱数

        int[] dp = new int[n + 1]; // 初始化动态规划数组

        dp[0] = 1; // 初始化dp[0]为1，表示钱数为0时有1种方案（不买书）

        // 遍历每种面额的书的价格，更新方案种数

        for (int ten = 0; ten * 10 <= n; ten++) {

            for (int twenty = 0; ten * 10 + twenty * 20 <= n; twenty++) {

                for (int fifty = 0; ten * 10 + twenty * 20 + fifty * 50 <= n; fifty++) {

                    for (int hundred = 0; ten * 10 + twenty * 20 + fifty * 50 + hundred * 100 <= n; hundred++) {

                        int sum = ten * 10 + twenty * 20 + fifty * 50 + hundred * 100;

                        dp[sum]++; // 更新对应的方案种数

                    }

                }

            }

        }

        // 输出方案种数

        System.out.println(dp[n]);

        scanner.close();

    }

}