动态规划：硬币兑换（有趣）
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
暴力算法思考
上来就是暴力思考，枚举每一种硬币的个数，然后判断是否可以组成金额
# coins[0]最多的数量为 k0 = amount // coins[0]
# coins[1]最多的数量为 k1 = amount // coins[1]
# coins[2]最多的数量为 k2 = amount // coins[2]m0 = amount // coins[0] # coins[0]最多的数量
m1 = amount // coins[1] # coins[1]最多的数量
m2 = amount // coins[2] # coins[22]最多的数量
min_cnt = amount + 1
for i in range(m0):for j in range(m1):for k in range(m2):cur_amount = coins[0] * i + coins[1] * j + coins[2] * k# 合起来金额正好相等if cur_amount == amount:# 当前的硬币数量cnt = i + j + kif cnt < min_cnt:min_cnt = cnt
if min_cnt == amount + 1:return -1
return min_cnt
上面的结构很明显可以用递归来解决，为啥呢？因为循环的深度与coins的长度相同，深度动态变化的循环通常可以转换成递归
def coin_change(coins, amount):min_count = float('inf') # 初始化最小硬币数为无穷大def dfs(index, remaining, current_count):nonlocal min_count# 基线条件：处理完所有硬币if index == len(coins):# 刚好凑成目标金额，更新最小计数if remaining == 0:if current_count < min_count:min_count = current_countreturn# 当前硬币的最大可能数量（剩余金额//硬币面值）max_num = remaining // coins[index]# 尝试使用0到max_num个当前硬币for num in range(0, max_num + 1):# 递归处理下一种硬币，更新剩余金额和当前计数dfs(index + 1, remaining - num * coins[index], current_count + num)# 从第0种硬币开始递归，初始剩余金额为amount，当前计数为0dfs(0, amount, 0)# 如果没找到有效组合，返回-1，否则返回最小计数return min_count if min_count != float('inf') else -1# 测试示例
print(coin_change([1, 2, 5], 11)) # 输出3（5+5+1）
print(coin_change([2], 3)) # 输出-1（无法组成）我们画出一个简易的递归树
按照使用某个硬币的数量划分集合
假如硬币兑换共有n种方案，我们要从这些方案中选择出最优的方案，也就是最少的硬币。我的简单想法是按照某个金额的数量来划分集合。例如样例中，按照硬币5的数量来划分所有的集合
- 集合1：使用0枚5元硬币的兑换方案
1，1，1，1，1，1，1，1，1，1，1 1，1，1，1，1，1，1，1，1，2 1，1，1，1，1，1，1，2，2 1，1，1，1，1，2，2，2 1，1，1，2，2，2，2 1，2，2，2，2，2 - 集合2：使用1枚5元硬币的兑换方案
5，2，2，2 5，1，1，2，2 5，1，1，1，1，2 5，1，1，1，1，1，1 - 集合3：使用2枚5元硬币的兑换方案
5，5，1
我们只要求解出每个集合中的最优方案，然后这些最优方案就是最后的最优方案。对于集合1，我们使用了0枚5元硬币。那么剩余了11-0*5=11元需要兑换。并且兑换的时候只能使用1元和2元。对于集合1我们同样可以将这些方案进行划分
| 集合 | 方案 |
|---|---|
| 使用0枚2元硬币 | 1，1，1，1，1，1，1，1，1，1，1 |
| 使用1枚2元硬币 | 1，1，1，1，1，1，1，1，1，2 |
| 使用2枚2元硬币 | 1，1，1，1，1，1，1，2，2 |
| 使用3枚2元硬币 | 1，1，1，1，1，2，2，2 |
| 使用4枚2元硬币 | 1，1，1，2，2，2，2 |
| 使用5枚2元硬币 | 1，2，2，2，2，2 |
对于集合2和集合3也可以按照相同的方式划分出新的集合。我们不断划分出更小的集合，如果求出了集合的最优值，然后不断比较就可以得到更大集合的更优值。
需要注意的是，每次传下去的金额数量需要减去当前的金额数量
例如我们想要知道全国身高最高的人，我们只要知道各个省的最高身高，为了知道各个省的最高身高，我们按照市将省进行划分，只要比较各个市的最大身高即可。
写到这里的时候，我突然想起了之前递归的两种方式，一种就是为了获取所有的遍历路径，将之前值不断传递下去，在叶子结点的时候就得到了最终的结果，另一种就是为了得到最终的值，会假设左子树和右子树的结果已经知道了，还原出原问题的解。一种就是自顶向下，一种就是自底向上。我们通常会写回溯算法，本质就是从根节点不断传递到叶子结点，需要把值传递下去，在叶子结点获取最终结果，但是同一个值既传递到左子树，又传递到右子树的时候，要不进行拷贝，这样左右子树互不干扰，要不就是先添加后删除，左子树用完之后，再给右子树使用
自顶向下不断将金额传递下去，在叶子结点判断是否符合要求
def coinChange(coins, amount):# 终止条件1：金额为0，需要0个硬币if amount == 0:return 0# 终止条件2：没有硬币但金额不为0，无法兑换if not coins:return -1 # -1表示无法兑换base_coin = coins[0]max_k = amount // base_coin # k的最大可能值（包含max_k）other_coins = coins[1:] # 剩余硬币min_total = float('inf') # 初始化为无穷大，方便比较最小值# 遍历k：使用0到max_k个base_coin（包含max_k）for k in range(max_k + 1):remain = amount - k * base_coin # 剩余金额# 递归求解子问题：用other_coins凑remain的最少硬币数sub_result = coinChange(other_coins, remain)# 只有子问题有有效解时，才计算总硬币数if sub_result != -1:total = k + sub_result # 总硬币数 = base_coin的数量k + 子问题的解if total < min_total:min_total = total# 如果所有k都无效，返回-1；否则返回最小值return min_total if min_total != float('inf') else -1按照是否使用某硬币划分集合
将所有方案分为两类：
- 集合 A：不使用面额 c 的硬币（仅用其他硬币凑金额）。例如5元
1，1，1，1，1，1，1，1，1，1，1 1，1，1，1，1，1，1，1，1，2 1，1，1，1，1，1，1，2，2 1，1，1，1，1，2，2，2 1，1，1，2，2，2，2 1，2，2，2，2，2 - 集合 B：至少使用 1 个面额 c 的硬币（先拿 1 个 c，再用所有硬币凑剩余金额）。
5，1，1，1，1，1，1 5，5，1 5，2，2，2 5，1，1，2，2 5，1，1，1，1，2
我们只要求出集合A和集合B的最小硬币数，即为最终的兑换数。
- 划分子问题：将硬币列表分为 使用当前硬币 和 不使用当前硬币 两类：
- 使用硬币 coins[0]：递归求解 amount - coins[0]（金额减少）。
- 不使用 coins[0]：递归求解 amount，但硬币列表移除 coins[0]（列表缩小）。
- 终止条件：
- 硬币列表为空：若 amount=0返回 1（唯一解：0 枚硬币）；否则返回 0（无解）
def coin_change(coins, amount):# 辅助递归函数：返回凑出金额amount的最少硬币数，无法凑出则返回无穷大def dfs(coins, amount):# Base Case 1: 金额为0，需要0个硬币if amount == 0:return 0# Base Case 2: 没有硬币但金额不为0，无法凑出，返回无穷大if not coins:return float('inf')# 选择使用当前硬币（coins[0]）use = float('inf')if amount >= coins[0]: # 只有剩余金额足够时，才能使用当前硬币use = dfs(coins, amount - coins[0]) + 1 # 用1个当前硬币，递归处理剩余金额# 不使用当前硬币，递归处理剩余硬币not_use = dfs(coins[1:], amount)# 返回两种选择中的最小值（最少硬币数）return min(use, not_use)result = dfs(coins, amount)# 若结果仍为无穷大，说明无法凑出，返回-1（按常规问题定义）return result if result != float('inf') else -1按最大面额划分集合
还有一种方式是使用面额来划分集合，这个兑换方案中最大的面额是多少
- 集合 A：最大面额是5元
5，5，1 5，2，2，2 5，1，1，2，2 5，1，1，1，1，2 5，1，1，1，1，1，1 - 集合 B：最大面额是2元
1，1，1，1，1，1，1，1，1，2 1，1，1，1，1，1，1，2，2 1，1，1，1，1，2，2，2 1，1，1，2，2，2，2 1，2，2，2，2，2 - 集合C：最大面额是1元
1，1，1，1，1，1，1，1，1，1，1
同样给出递归算法
def count_combinations(coins, amount):# 先对硬币排序，确保按面额从小到大（方便按最大面额划分）coins.sort()def dfs(max_idx, remaining):# Base Case 1: 剩余金额为0，找到1种有效组合if remaining == 0:return 1# Base Case 2: 无可用硬币或金额为负，无有效组合if max_idx < 0 or remaining < 0:return 0# 当前最大面额的硬币current_coin = coins[max_idx]# 最多可使用 current_coin 的次数max_uses = remaining // current_cointotal = 0# 尝试使用 0 到 max_uses 次 current_coinfor k in range(0, max_uses + 1):# 递归计算：使用k次current_coin后，剩余金额由更小面额（max_idx-1）解决total += dfs(max_idx - 1, remaining - k * current_coin)return total# 初始最大面额索引为最后一个元素（面额最大）return dfs(len(coins) - 1, amount)终极递归
在零钱兑换问题中，递归解法的核心思想是将问题分解为子问题：对于当前金额，尝试使用每种硬币，递归求解剩余金额的最少硬币数。以下是两种递归实现方式及其优化方案：
⚙️ 一、基础递归解法（纯暴力，效率低）
- 终止条件：
- amount == 0：返回 0（无需硬币）。
- amount < 0：返回 -1（无解）。
2.状态转移：
- 遍历每种硬币 coin，递归计算 amount - coin的最少硬币数。
- 若子问题有解，更新全局最小值：minCount = min(minCount, subResult + 1)。
3.返回值：若最小值未更新（仍为 Infinity），返回 -1；否则返回最小值。
def coinChange(coins, amount):if amount == 0: return 0if amount < 0: return -1min_count = float('inf')for coin in coins:# 递归求解子问题sub_result = coinChange(coins, amount - coin)if sub_result == -1: continue # 子问题无解则跳过min_count = min(min_count, sub_result + 1)return min_count if min_count != float('inf') else -1
🧠 二、优化递归：记忆化搜索（Memoization）
- 缓存子问题结果：用数组 memo存储 memo[amount]表示金额 amount的最少硬币数。
- 避免重复计算：递归前先查缓存，若已计算则直接返回结果。
def coinChange(coins, amount):memo = [-1] * (amount + 1) # 初始化缓存def dp(remain):if remain == 0: return 0if remain < 0: return -1if memo[remain] != -1: # 缓存命中return memo[remain]min_count = float('inf')for coin in coins:sub_result = dp(remain - coin)if sub_result == -1: continuemin_count = min(min_count, sub_result + 1)# 更新缓存memo[remain] = min_count if min_count != float('inf') else -1return memo[remain]return dp(amount)