最少钱币数

试题名称：最少钱币数
问题描述：这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，可以用 5 个 2 元、1个 5 元，或者 3 个 5 元，或者 1 个 5 元、1个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。
你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。
输入形式：输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M<= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K个互不相同的钱币面值 Ki(1 <= Ki <= 1000)。输入M = 0时结束。
输出形式：每个测试用例输出一行，即凑成钱数值 M 最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。
样例输入：
15
6 2 5 10 20 50 100
1
1 2
0
样例输出：
2
Impossible

Java实现

import java.util.Scanner;

public class LeastCoin {
    public static void main(String[] args) {
        int[] coins = new int[10]; // 硬币面值数组
        int money = 0; // 待凑金额
        int kind = 0; // 硬币种类数

        while (true) {
            money = new Scanner(System.in).nextInt();
            if (money == 0) {
                break; // 结束标记
            }
            int[] dp = new int[money + 1]; // 动态规划数组
            dp[0] = 0; // 初始化第一个元素为0，凑0元需要0个硬币
            kind = new Scanner(System.in).nextInt();
            for (int i = 0; i < kind; i++) {
                coins[i] = new Scanner(System.in).nextInt(); // 读入硬币面值，存入数组coins
            }
            for (int i = 1; i <= money; i++) {
                dp[i] = 99999; // 初始化数组dp，设置dp[i]为无穷大
            }
            // 从凑1元开始，到money元为止
            for (int i = 1; i <= money; i++) {
                for (int j = 0; j < kind; j++) {
                    if (i >= coins[j] && dp[i - coins[j]] + 1 < dp[i]) {
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                }
            }
            if (dp[money] == 99999) {
                System.out.println("Impossible");
            } else {
                System.out.println(dp[money]);
            }
        }
    }
}

Python实现

coins = []

while True:
    money = int(input("待凑金额："))
    if money == 0:
        break
    dp = [0]
    kind = int(input("硬币种类数："))
    for i in range(kind):
        coins.append(int(input(f"第{i + 1}个硬币面值：")))
    for i in range(1, money + 1):
        dp.append(99999)
    for i in range(1, money + 1):
        for j in range(kind):
            if i >= coins[j] and dp[i - coins[j]] + 1 < dp[i]:
                dp[i] = dp[i - coins[j]] + 1
    if dp[money] == 99999:
        print("Impossible")
    else:
        print(dp[money])