BGN64 硬币凑钱

思路

题目要求：银行有面值为 1 元、5 元、7 元的硬币，每种数量无限，求凑出 元所需的最少硬币数。

这是一道非常经典的完全背包 / 硬币找零问题。

第一反应可能是贪心 —— 尽量多用大面值硬币。但这里贪心是不对的！比如 ，贪心会先用 1 个 7 元，剩下 3 元只能用 3 个 1 元，总共 4 枚。但实际上 2 个 5 元就搞定了，只要 2 枚。

所以我们需要用动态规划。

状态定义

设 表示凑出金额 所需的最少硬币数。

转移方程

对于每个金额 ，我们尝试用每种硬币 ：

$$

初始值

（凑出 0 元不需要硬币），其余初始化为一个很大的值。

举个例子，：

  • （一个 5 元）
  • （一个 7 元）
  • （两个 5 元）

整个过程就是从小到大把每个金额的最优解算一遍，最终 就是答案。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0;
    int coins[] = {1, 5, 7};
    for (int i = 1; i <= n; i++) {
        for (int c : coins) {
            if (c <= i && dp[i - c] + 1 < dp[i]) {
                dp[i] = dp[i - c] + 1;
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        int[] coins = {1, 5, 7};
        for (int i = 1; i <= n; i++) {
            dp[i] = n + 1;
            for (int c : coins) {
                if (c <= i && dp[i - c] + 1 < dp[i]) {
                    dp[i] = dp[i - c] + 1;
                }
            }
        }
        System.out.println(dp[n]);
    }
}

n = int(input())
dp = [0] + [n + 1] * n
for i in range(1, n + 1):
    for c in (1, 5, 7):
        if c <= i and dp[i - c] + 1 < dp[i]:
            dp[i] = dp[i - c] + 1
print(dp[n])

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', line => {
    const n = parseInt(line.trim());
    const dp = new Array(n + 1).fill(n + 1);
    dp[0] = 0;
    const coins = [1, 5, 7];
    for (let i = 1; i <= n; i++) {
        for (const c of coins) {
            if (c <= i && dp[i - c] + 1 < dp[i]) {
                dp[i] = dp[i - c] + 1;
            }
        }
    }
    console.log(dp[n]);
    rl.close();
});

复杂度分析

  • 时间复杂度：，遍历每个金额，对每个金额检查 3 种硬币。
  • 空间复杂度：，需要一个长度为 的 dp 数组。

总结

硬币找零是动态规划的入门经典题。这道题最重要的 takeaway 就是：贪心在硬币问题上不一定对，面值组合不满足贪心条件时（比如这里的 1、5、7），必须用 DP 才能保证最优。记住这个转移方程，以后遇到类似的"最少物品凑目标值"问题，直接套就行。