题目链接：https://leetcode.cn/problems/coin-change/description/?envType=problem-list-v2&envId=2cktkvj

1、核心思路

这是一个完全背包问题（每种硬币无限使用）。

状态定义
dp[i] = 凑成金额 i 所需的最少硬币数

状态转移
对于每个金额 i，我们可以选择任意一个硬币 coin：

dp[i] = min(dp[i], dp[i - coin] + 1)
意思是：凑成 i 的最少硬币数 = 凑成 i - coin 的最少硬币数 + 1（使用当前这枚硬币）

初始化
dp[0] = 0（凑成 0 元需要 0 个硬币）

dp[1…amount] = float(‘inf’)（初始化为无穷大，表示不可达）

图解示例
示例：coins = [1, 2, 5], amount = 11
初始化

dp[0] = 0
dp[1…11] = inf

最终 dp[11] = 3（5+5+1）

2.代码实现

版本一：标准 DP（推荐）

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[i] = 凑成金额 i 需要的最少硬币数
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for i in range(1, amount + 1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != float('inf') else -1

版本二：先遍历硬币（更符合完全背包）

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != float('inf') else -1

两种遍历顺序的区别：

版本一：按金额遍历（外层 i，内层 coin）→ 更直观

版本二：按硬币遍历（外层 coin，内层 i）→ 标准完全背包写法

注：
float(‘inf’) = 无穷大，用于初始状态表示"无法到达"
任何实际值都比它小，所以 min(inf, 实际值) = 实际值
最后检查是否还是 inf，如果是则返回 -1

3、优化：BFS 解法（另一种思路）

把问题看作图的最短路径，用 BFS 从 amount 向下搜索：

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        queue = deque([amount])
        visited = set([amount])
        steps = 0
        
        while queue:
            steps += 1
            for _ in range(len(queue)):
                curr = queue.popleft()
                for coin in coins:
                    next_val = curr - coin
                    if next_val == 0:
                        return steps
                    if next_val > 0 and next_val not in visited:
                        visited.add(next_val)
                        queue.append(next_val)
        
        return -1

BFS 优势：一旦找到就是最优解，不需要遍历所有金额。
但 DP 更通用，适合各种变体。

4、复杂度分析

5、关键点总结

状态定义：dp[i] = 凑成金额 i 的最少硬币数

转移方程：dp[i] = min(dp[i], dp[i-coin] + 1)

初始化：dp[0] = 0，其他为无穷大

无限硬币：完全背包，遍历顺序正着来（允许重复使用）

无解判断：如果 dp[amount] 仍是无穷大，返回 -1

附-背包思维：

---

一、什么是背包问题？

想象一个场景：

你有一个背包，最多能装 W 公斤的东西。
面前有若干物品，每个物品有重量和价值。
问：怎样装才能让背包里的总价值最大？

这就是背包问题的原始模型。

---

二、背包问题的分类

类型	特点	代表题目
0/1 背包	每个物品只能用一次	分割等和子集
完全背包	每个物品无限用	零钱兑换
多重背包	每个物品有有限数量	较少出现
分组背包	每组选一个	较少出现

---

三、0/1 背包（最基础）

问题描述

有 n 个物品，第 i 个物品重量为 w[i]，价值为 v[i]。
背包容量为 W。每个物品只能选一次，求最大价值。

核心思想

对于每个物品，只有两种选择：选 或 不选。

状态定义

dp[i][j] = 考虑前 i 个物品，背包容量为 j 时的最大价值

状态转移

dp[i][j] = max(
    dp[i-1][j],                    // 不选第 i 个物品
    dp[i-1][j - w[i]] + v[i]       // 选第 i 个物品（需要腾出空间）
)

代码（二维）

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(W + 1):
            if j < weights[i-1]:
                dp[i][j] = dp[i-1][j]  # 装不下
            else:
                dp[i][j] = max(dp[i-1][j], 
                               dp[i-1][j - weights[i-1]] + values[i-1])
    
    return dp[n][W]

空间优化（一维）

关键：从后往前遍历，防止物品被重复使用

def knapsack_01_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        # 从后往前，确保每个物品只用一次
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[W]

为什么从后往前？

假设重量=2，价值=3

从前往后（错误）：
dp[2] = max(dp[2], dp[0]+3) = 3
dp[4] = max(dp[4], dp[2]+3) = 6  ← 同一个物品用了两次！

从后往前（正确）：
dp[4] = max(dp[4], dp[2]+3) = 3  ← 此时 dp[2] 还没被更新
dp[2] = max(dp[2], dp[0]+3) = 3

---

四、完全背包（零钱兑换）

与 0/1 背包的区别

• 0/1 背包：每个物品只能用一次
• 完全背包：每个物品可以用无限次

状态转移（相同）

dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])
                              ↑ 注意：这里是 dp[i] 不是 dp[i-1]

关键区别

完全背包允许重复使用，所以：

• 0/1 背包：dp[i-1][j - w]（上一个物品）
• 完全背包：dp[i][j - w]（当前物品，可以继续用）

代码（一维）

def knapsack_complete(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        # 从前往后，允许物品被重复使用
        for j in range(weights[i], W + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[W]

零钱兑换就是完全背包的变体

• 硬币面额 = 物品重量
• 硬币个数 = 物品价值（每个硬币价值为 1）
• 求：装满背包的最小硬币数

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:  # 完全背包：外层物品
        for i in range(coin, amount + 1):  # 从前往后
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

---

五、背包问题对比表

特性	0/1 背包	完全背包
物品使用次数	0 或 1 次	任意次
遍历顺序	从后往前	从前往后
典型题目	分割等和子集	零钱兑换
状态含义	最大价值	最大价值/最小个数

---

六、常见变体题目

1. 分割等和子集（0/1 背包）

# 能否将数组分成两个和相等的子集
def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):  # 0/1 背包：从后往前
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

2. 零钱兑换 II（完全背包）

# 凑成总金额的硬币组合数
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

3. 组合总和 IV（排列数）

# 注意：这是排列，不是组合
def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    
    for i in range(1, target + 1):
        for num in nums:
            if i >= num:
                dp[i] += dp[i - num]
    
    return dp[target]

---

七、背包思想的核心公式

模板总结

# 0/1 背包（最多选一次）
for 物品 in 物品列表:
    for j in range(容量, 重量-1, -1):  # 从后往前
        dp[j] = max(dp[j], dp[j-重量] + 价值)

# 完全背包（无限选）
for 物品 in 物品列表:
    for j in range(重量, 容量+1):      # 从前往后
        dp[j] = max(dp[j], dp[j-重量] + 价值)

# 求方案数（组合）
dp[0] = 1
for 物品 in 物品列表:
    for j in range(重量, 容量+1):
        dp[j] += dp[j-重量]

# 求方案数（排列）
dp[0] = 1
for j in range(1, 容量+1):
    for 物品 in 物品列表:
        if j >= 重量:
            dp[j] += dp[j-重量]

---

八、记忆口诀

0/1 背包逆序走，每个物品只用一次
完全背包正序走，无限使用随便拿
求最大用 max，求最小用 min
求方案数用加号，组合物品在外层
排列金额在外层

---

九、实际应用场景

1. 资源分配：有限资源如何分配最优
2. 时间管理：有限时间内完成最多任务
3. 投资组合：有限资金如何投资回报最大
4. 机器学习：特征选择
5. 密码学：背包加密算法

---

背包思想核心就是：

1. 状态定义：dp 代表什么
2. 转移方程：选或不选当前物品
3. 遍历顺序：决定物品能否重复使用