难度: Medium
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
示例 2：
输入：coins =[2], amount =3输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
示例 4：
输入：coins = [1], amount = 1 输出：1
示例 5：
输入：coins = [1], amount = 2 输出：2
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104注意：本题与主站 322 题相同： https://leetcode-cn.com/problems/coin-change/
运行时间: 64 ms
内存: 16.0 MB
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = 1 << amount
for step in count():
if dp & 1:
return step
new = 0
for c in coins:
new |= dp >> c
if new == dp:
return -1
dp = new
题解中采用了一种基于位运算的动态规划方法来解决零钱兑换问题。首先，使用一个整数`dp`的位表示，其中第i位的值为1表示能够用硬币组合凑成金额i。初始化`dp`为1左移`amount`位，表示只有amount位为1，其余均为0。使用一个无限循环，每次循环中检查第0位，如果为1，则返回当前的步数（已经找到最小硬币组合）。对于每种硬币面值，将`dp`右移该硬币面值的位数，通过位或操作更新`dp`，如果在某次循环中`dp`未发生变化，说明无法通过已有硬币组合凑出更多金额，此时返回-1。
时间复杂度: O(amount * k)
空间复杂度: O(1)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = 1 << amount # 初始化dp，将第amount位设置为1，其他位为0
for step in count(): # 从0开始计数step
if dp & 1: # 如果第0位是1，表示可以用硬币组合凑出金额0
return step # 返回步数，即最小硬币数
new = 0 # 初始化新状态为0
for c in coins: # 遍历每种硬币
new |= dp >> c # 将dp右移硬币面值位，通过位或更新new
if new == dp: # 如果状态没有改变
return -1 # 无法凑出新的金额，返回-1
dp = new # 更新dp为新的状态
在本题解中，使用位运算来表示状态而不是数组或哈希表主要是为了利用位运算的高效性和紧凑性。位运算允许我们在单个整数中存储和操作多个状态，这样可以减少内存的占用，并且位运算的操作（如位移和位或）通常比数组或哈希表的操作更快。同时，位运算还能简化某些逻辑，如状态转移，因为可以通过位移和位或直接实现状态的更新，而不需要逐个元素的迭代处理。这种方法尤其适用于涉及连续整数范围的问题，如本问题中的金额表示。
如果在某次循环中`dp`未发生变化，意味着通过当前的硬币面值组合无法生成新的金额。这通常发生在硬币的面值无法组合出介于已有金额之外的新金额时。例如，假设有硬币面值为2和5，要凑的金额是3。初始`dp`设置为第3位为1（表示目标是3），但由于无论如何组合2和5都无法凑出3（2和5都无法减少到1），所以每次更新`dp`后，状态不会包括第0位为1的情况，因此`dp`最终不会变化，算法就会返回-1，表示无法凑出目标金额。
初始化`dp`为1左移`amount`位是一种表示目标金额可以通过0枚硬币直接达到的方法。在这种初始化方式中，将第`amount`位设置为1而其他位为0意味着起始状态只考虑能通过硬币组合凑出金额`amount`的可能性，而忽略其他所有金额。这样的设置允许算法从特定的目标金额开始向下计算，每次通过硬币面值的位移来逐步检查能否凑出较小的金额。这是一种从目标金额向零金额“倒推”的方法，与传统的动态规划从0开始向目标金额累加的方式相反。