题解 | #硬币凑钱#

题目链接

题目描述

银行拥有面值为1元、5元与7元的硬币若干，每种面值的硬币数量均视为无限。现在需要支付恰好 $S$ 元，求出所需硬币数量的最小值。

解题思路

这是一个典型的“完全背包”求最优解的问题。我们可以使用动态规划来求解。

我们定义一个一维数组 $dp$ ，其中 $dp[j]$ 表示凑成总金额为 $j$ 所需的最少硬币数量。我们的目标是求 $dp[S]$ 。

首先，初始化 $dp$ 数组。 $dp[0] = 0$ ，因为凑成金额0需要0个硬币。对于其他金额 $j > 0$ ，我们应该将 $dp[j]$ 初始化为一个非常大的数（表示无穷大），代表当前还无法凑成该金额。

然后，我们遍历每一种硬币。对于面值为 $v_i$ 的硬币（这里是1, 5, 7），我们来更新 $dp$ 数组。对于一个金额 $j$ （从 $v_i$ 到 $S$ ），凑成它的方法可以是在凑成 $j - v_i$ 的基础上，再加一枚面值为 $v_i$ 的硬币。此时，总硬币数为 $dp[j - v_i] + 1$ 。我们需要在所有可能性中取最小值。

由此，我们可以得到状态转移方程： $dp[j] = \min(dp[j], dp[j - v_i] + 1)$

这个方程的含义是：凑成金额 $j$ 所需的最少硬币数，是当前已知的 $dp[j]$ 和 “凑成 $j-v_i$ 的最少硬币数再加1” 这两者中的较小值。

完整的算法流程如下：

创建一个大小为 $S+1$ 的数组 $dp$ ，并将 $dp[0]$ 初始化为0，其余初始化为无穷大。
定义硬币面值数组 coins = {1, 5, 7}。
对于每一种硬币 v in coins：
对于从 v 到 $S$ 的每一个金额 $j$ ：
更新 $dp[j] = \min(dp[j], dp[j - v] + 1)$ 。
遍历完所有硬币后， $dp[S]$ 就是最终的答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9; // 代表无穷大

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int s;
    cin >> s;

    vector<int> coins = {1, 5, 7};
    vector<int> dp(s + 1, INF);
    dp[0] = 0;

    // 遍历每种硬币
    for (int coin : coins) {
        // 遍历背包容量（金额）
        for (int j = coin; j <= s; ++j) {
            if (dp[j - coin] != INF) { // 确保 j-coin 是可达的
                dp[j] = min(dp[j], dp[j - coin] + 1);
            }
        }
    }

    cout << dp[s] << "\n";

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();

        int[] coins = {1, 5, 7};
        int[] dp = new int[s + 1];
        final int INF = 1_000_000_000; // 代表无穷大
        
        Arrays.fill(dp, INF);
        dp[0] = 0;

        // 遍历每种硬币
        for (int coin : coins) {
            // 遍历背包容量（金额）
            for (int j = coin; j <= s; j++) {
                if (dp[j - coin] != INF) { // 确保 j-coin 是可达的
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
        }

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

def solve():
    s = int(input())
    
    coins = [1, 5, 7]
    INF = float('inf')
    dp = [INF] * (s + 1)
    dp[0] = 0

    # 遍历每种硬币
    for coin in coins:
        # 遍历背包容量（金额）
        for j in range(coin, s + 1):
            if dp[j - coin] != INF:
                dp[j] = min(dp[j], dp[j - coin] + 1)
    
    print(dp[s])

solve()

算法及复杂度

算法：动态规划（完全背包求最优解）
时间复杂度： $O(N \cdot S)$ ，其中 $N$ 是硬币种数（本题为常数3）， $S$ 是目标金额。因此复杂度为 $O(S)$ 。
空间复杂度： $O(S)$ ，用于存储 dp 数组。