BM70　兑换零钱(一)¶

中等通过率 33.93%python3核心代码模式样例通过牛客 AC动态规划

牛客原题　源码

讲解章节：背包问题

一句话

完全背包求最少硬币数，改用位集合按「枚数」分层并行推进。

解题思路¶

这题考什么¶

课本写法与工程写法的取舍，两种都要看懂。

写法一（课本式完全背包），见背包问题：

状态定义：dp[c] = 凑出金额 c 所需的最少硬币数，dp[0] = 0，其余取正无穷。
转移方程：

    dp[c] = min(dp[c], dp[c - v] + 1)     对每种面值 v，容量 c 从 v 到 aim **正序**

容量正序遍历是完全背包的标志：dp[c-v] 可能已经在本轮被同一面值更新过，
于是同一种硬币自然地被允许重复使用。倒序则退化成 01 背包（每种硬币只能用一次），
求出来是另一道题的答案。结束时 dp[aim] 仍是正无穷就返回 -1。

写法二（本文件采用的位集合分层 BFS）：把「最少枚数」看成最短路层数。

S[t] = 恰好用 t 枚硬币能凑出的金额集合
S[t] = 所有 (S[t-1] + v) 的并集        对每种面值 v

把集合压成一个大整数的位集合：第 c 位为 1 表示金额 c 可达。于是「整个集合每个元素加 v」就是左移 v 位，「并集」就是按位或：

nxt = (S << v1) | (S << v2) | ...        再与掩码、与已访问集合的补取交

每一次移位由 CPython 在 C 层一口气处理 5001 个比特，抵得上逐格转移里的几千次 Python 级迭代。第一次让第 aim 位变成 1 的层数就是答案——广度优先保证首次到达即最少枚数；某一层没有任何新金额出现（nxt == 0）说明可达集合已经封闭，此后再推也不会变，返回 -1。

数据规模与复杂度¶

n <= 1e4，每个面值 <= 1e4，aim <= 5000，时限 4 秒（其他语言）。

课本写法：n * aim = 1e4 * 5e3 = 5e7 次 Python 级迭代；即使先去重把面值数压到 <= aim，也还有 5e3 * 5e3 = 2.5e7 次。判题机比本机慢数倍，这个量级在 4 秒里没有指望，所以被否决。换成 C++ 则轻松通过——这条取舍是 Python 特有的。
本解法：每层只做「面值数」次大整数移位与按位或，每次的代价正比于 aim/字长；层数与面值数此消彼长（面值多则答案层数少，面值少则每层移位少），总开销比逐格转移低若干个数量级。空间 O(aim/字长)，只有 seen、frontier 两个约 5000 位的整数。

坑在哪¶

aim == 0 要返回 0（一枚不用就凑出 0 元），不是 -1。这条出口也保证了后面 1 << (aim+1) 的掩码至少有 2 位。
面值可能大于 aim（题面允许面值到 1e4，而 aim 只到 5000）。不滤掉它们，左移会把 1 推到掩码之外，白白拉长大整数、拖慢每一次移位。
掩码 & mask 不能省。位集合每层都会向高位膨胀，不截断的话整数越来越长，移位成本随之上升，而超过 aim 的金额对答案毫无用处。
& ~seen 是 BFS 的「不重复入队」。省掉它虽然不影响正确性，但 frontier 会不断把老金额带进下一层，层层膨胀，也就失去了 nxt == 0 的终止判据。
nxt == 0 是唯一的无解判据：可达集合不再增长，说明它已经封闭而 aim 不在其中。换成「循环 aim 次仍未命中」也对，但要多跑很多空层。
位集合的第 0 位代表金额 0，seen 与 frontier 都从 1（二进制的第 0 位）起手；初始化成 0 会让整个搜索从空集出发，永远推不出任何金额。
题面已保证 arr 内的值互不重复，集合推导式顺带完成去重，主要作用还是滤掉超过 aim 的面值。

样例复核¶

arr = [5,2,3]、aim = 20。第 4 层首次让第 20 位置 1（5+5+5+5），返回 4，与期望输出一致。

参考实现¶

solutions/nowcoder/BM70/sol.py
from typing import List, Optional


class Solution:
    def minMoney(self, arr: List[int], aim: int) -> int:
        if aim <= 0:
            return 0                                    # 凑 0 元不需要任何硬币
        # 去重（题面本已保证不重复）并丢掉大于 aim 的面值：它们只会把位集合推出掩码之外
        coins = {v for v in arr if 0 < v <= aim}
        if not coins:
            return -1                                   # 没有可用面值，凑不出正的 aim
        mask = (1 << (aim + 1)) - 1                      # 低 aim+1 位分别代表金额 0..aim
        target = 1 << aim                                # 只要这一位被点亮就说明凑出了 aim
        # 位集合：第 c 位为 1 表示金额 c 可达。seen 是历史全集，frontier 是本层新增的金额。
        # 两者都从「第 0 位」起手，代表用 0 枚硬币可以凑出金额 0
        seen = frontier = 1
        steps = 0                                        # 已经用掉的硬币枚数，即 BFS 的层数
        while True:
            nxt = 0
            for v in coins:
                nxt |= frontier << v                     # 左移 v 位 = 整个集合里每个金额都加 v
            nxt &= mask & ~seen                          # 截掉超出 aim 的位，去掉已访问的金额
            if not nxt:
                return -1                                # 可达集合不再增长，说明它已封闭且不含 aim
            steps += 1
            if nxt & target:
                return steps                             # 广度优先：首次到达即最少枚数
            seen |= nxt
            frontier = nxt                               # 下一层只从本层新增的金额出发

BM70 兑换零钱(一)¶