DSA Interview Prep · 课时

零钱兑换与最低成本爬楼梯

Q: 「零钱兑换与最低成本爬楼梯」这节课中我会学到什么？

建立零钱兑换和最低成本爬楼梯的递推式，选择正确的 DP 方向，并手动跟踪表格计算。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

建立零钱兑换和最低成本爬楼梯的递推式，选择正确的 DP 方向，并手动跟踪表格计算。

零钱兑换与最低成本爬楼梯 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

硬币兑换：问题定义

硬币兑换（LeetCode #322）给定若干硬币面额和一个目标金额。请找出凑出该准确金额所需的最少硬币数量。每种面额的硬币都有无限枚。这是一个经典的无界背包变体——每个物品（硬币）都可以使用任意次数。这是最重要的 DP 问题之一，因为它考查您从零开始构造递推关系的能力。

# Problem examples:
# coins=[1,5,6,9], amount=11 -> 2 (5+6 or 2+9? no: 5+6=11 YES)
# coins=[2],       amount=3  -> -1 (impossible)
# coins=[1,2,5],   amount=11 -> 3 (5+5+1)
# coins=[186,419,83,408], amount=6249 -> 20

# Key choices:
# - Try each coin denomination at each step
# - Minimum coins = 1 + minimum(coins to make amount - coin)
# - If amount < 0: impossible
# - If amount = 0: done (0 coins)

print('Coin change: unbounded knapsack, find minimum count')

硬币兑换：递推关系推导

定义 dp[i] = 凑出金额 i 所需的最少硬币数。对于每个金额 i，尝试使用每种硬币 c：若 i >= c，则 dp[i] = min(dp[i], 1 + dp[i-c])。其中的“1”表示刚刚使用的一枚硬币；dp[i-c] 是凑出剩余金额的最优解。这一方法假设硬币数量无限。基础情况是：dp[0] = 0。将其他所有条目初始化为无穷大，表示“尚不可达”。

def coin_change(coins, amount):
    # dp[i] = min coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base: 0 coins for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2
print(coin_change([2], 3))             # -1
print(coin_change([1, 2, 5], 11))      # 3

# Trace dp for coins=[1,5] amount=6:
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1, dp[6]=2

硬币兑换：贪心法为何失败

贪心法（总是选择能够使用的最大面额硬币）在硬币兑换问题中会失败。例如：coins=[1, 3, 4]，amount=6。贪心法先选择 4，再用 1+1，共需要 3 枚硬币。最优方案是 3+3，只需要 2 枚硬币。对于标准面额（1、5、10、25 美分），贪心法有效，因为这些面额恰好满足贪心性质。但对于任意硬币集合，则必须使用 DP。这是面试中的经典考点——说明贪心法会失败并解释原因，可以体现出较强的分析能力。

# Greedy failure example:
# coins=[1,3,4], amount=6
# Greedy: 4 (rem=2), 1 (rem=1), 1 (rem=0) -> 3 coins
# Optimal: 3 (rem=3), 3 (rem=0) -> 2 coins

def coin_change_greedy_wrong(coins, amount):
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    for coin in coins_sorted:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

print('Greedy:', coin_change_greedy_wrong([1,3,4], 6))  # 3 (WRONG)
print('DP:    ', coin_change([1,3,4], 6))               # 2 (CORRECT)

硬币兑换 II：计算方案数

硬币兑换 II（LeetCode #518）要求计算凑出目标金额的方案数（而不是最少硬币数）。递推关系也随之改变：不再取最小值，而是求和。对于每种硬币，使用 dp[i] += dp[i-coin]。填充顺序很重要：为了让每种组合只被计算一次，应将硬币放在外层循环，将金额放在内层循环。颠倒循环顺序会计算排列数，而不是组合数（这是另一个问题）。

def coin_change_ii(coins, amount):
    # dp[i] = number of ways to make amount i
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make amount 0: use no coins

    # Outer loop: coins -- ensures each coin type processed once
    for coin in coins:
        # Inner loop: amounts
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

print(coin_change_ii([1, 2, 5], 5))   # 4: [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
print(coin_change_ii([2], 3))          # 0: impossible
print(coin_change_ii([10], 10))        # 1

# Key: coin outer, amount inner = COMBINATIONS (unordered)
# Reverse (amount outer, coin inner) = PERMUTATIONS (ordered)

最小代价爬楼梯：问题定义

最小代价爬楼梯（LeetCode #746）给定一段楼梯，每一级都有一个代价。您每次可以爬 1 级或 2 级。请找出到达楼顶（最后一级之上的位置）的最小代价。您可以免费从第 0 级或第 1 级开始。这个问题巧妙地结合了爬楼梯问题的递推关系和硬币兑换问题的代价最小化模式，是连接这两个问题的自然桥梁。

# cost = [10, 15, 20]
# Pay cost[i] to leave step i
# You can step to i+1 or i+2
# Goal: reach top (index 3) with minimum cost

# Path options:
# Start at 0: cost 10, go to 2: cost 20, done -> 30
# Start at 1: cost 15, go to 3: done -> 15  <- OPTIMAL
# Start at 0: cost 10, go to 1: cost 15 -> 25

cost = [10, 15, 20]
# Optimal: start at step 1, pay 15, jump to top -> cost = 15
print('Expected:', 15)

最小代价爬楼梯：递推关系

定义 dp[i] = 到达第 i 级所需的最小代价。您可以从第 i-1 级出发并支付 cost[i-1]，也可以从第 i-2 级出发并支付 cost[i-2]。因此，dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。基础情况是：dp[0] = 0（从楼梯前开始，不需要付费），dp[1] = 0（也可以从第 1 级开始，不需要付费）。答案是 dp[n]，其中 n = len(cost)。

def min_cost_climbing_stairs(cost):
    n = len(cost)
    # dp[i] = minimum cost to reach step i
    # Steps 0 to n; step n is the top (goal)
    dp = [0] * (n + 1)
    # dp[0] = 0 (free to start here)
    # dp[1] = 0 (free to start here)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1],   # step from i-1
                    dp[i-2] + cost[i-2])    # jump from i-2
    return dp[n]

print(min_cost_climbing_stairs([10, 15, 20]))      # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1]))  # 6

最小代价爬楼梯：空间优化

由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，因此可以像处理斐波那契数列一样，使用两个变量将空间复杂度降至 O(1)。用 prev2 和 prev1 替代数组，并在每一步更新它们。这是面试官希望您在给出 O(n) 表格解法后完成的标准单行优化。请主动说明：“由于我们只需要最后两个值，因此可以将空间复杂度降至 O(1)。”

def min_cost_optimised(cost):
    n = len(cost)
    prev2, prev1 = 0, 0  # dp[0] and dp[1]
    for i in range(2, n + 1):
        curr = min(prev1 + cost[i-1], prev2 + cost[i-2])
        prev2, prev1 = prev1, curr
    return prev1

print(min_cost_optimised([10, 15, 20]))  # 15
print(min_cost_optimised([1,100,1,1,1,100,1,1,100,1]))  # 6

# Alternative: directly use cost array as rolling storage
def min_cost_v2(cost):
    n = len(cost)
    for i in range(2, n):
        cost[i] += min(cost[i-1], cost[i-2])
    return min(cost[-1], cost[-2])

from copy import deepcopy
cost_test = [10,15,20]
print(min_cost_v2(deepcopy(cost_test)))  # 15

另一种 DP 定义方式

有些问题存在多种有效的 DP 定义方式。对于最小代价爬楼梯，您可以将 dp[i] 定义为离开第 i 级的最小代价（支付 cost[i]，然后选择前往 i+1 级或 i+2 级）。此时从右向左填充：dp[i] = cost[i] + min(dp[i+1], dp[i+2])，答案是 min(dp[0], dp[1])。两种定义方式都正确。请练习清楚地说明您选择了哪种定义方式以及原因——这能体现您对 DP 的熟练程度。

def min_cost_alternative(cost):
    n = len(cost)
    # dp[i] = min cost when starting FROM step i
    # Fill right to left
    dp = cost[:] + [0]  # dp[n] = 0 (already at top)
    for i in range(n - 1, -1, -1):
        # Pay cost[i], then choose i+1 or i+2
        if i + 2 <= n:
            dp[i] = cost[i] + min(dp[i+1], dp[i+2])
        else:
            dp[i] = cost[i] + dp[i+1]
    # Can start at step 0 or step 1
    return min(dp[0], dp[1])

print(min_cost_alternative([10, 15, 20]))  # 15
print(min_cost_alternative([1,100,1,1,1,100,1,1,100,1]))  # 6

连接硬币兑换与爬楼梯问题

硬币兑换和最小代价爬楼梯都属于同一种 DP 模式：在每一步从有限的选项中做出选择，并针对整个选择序列优化某个目标。两者的差异只是表面上的：硬币兑换跟踪数量（每枚硬币加 1），爬楼梯跟踪代价（每一步加上 cost[i]）。识别这种共同结构后，您就可以将新的 DP 问题映射到熟悉的模板上来解决。

# Shared pattern:
# dp[state] = optimise(dp[prev_state_1] + cost_1,
#                      dp[prev_state_2] + cost_2, ...)

# Coin change:  dp[amount] = min(1 + dp[amount - coin] for coin in coins)
# Min stair:    dp[step]   = min(cost[step-1]+dp[step-1], cost[step-2]+dp[step-2])
# Max path sum: dp[cell]   = max(dp[top], dp[left]) + grid[cell]
# House robber: dp[house]  = max(dp[house-1], dp[house-2] + value[house])

# All four are the SAME pattern with different:
# - State representation
# - Number of choices per state
# - Objective (min/max)
# - Transition cost
print('DP pattern: state + choices + objective + cost = template')

完全平方数的最少数量

完全平方数（LeetCode #279）要求计算总和为 n 的完全平方数（1、4、9、16……）的最少数量。这与硬币兑换问题完全相同，只是“硬币”变成了完全平方数。先生成不超过 n 的所有完全平方数，然后运行硬币兑换算法。DP 的 time 复杂度为 O(n * sqrt(n))。拉格朗日四平方定理告诉我们，答案最多为 4，因此也可以使用 O(sqrt(n)) 的数学方法——但预期解法仍然是 DP。

import math

def num_squares(n):
    # Generate all perfect squares up to n
    squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]
    # Coin change with squares as 'coins'
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for sq in squares:
            if i >= sq:
                dp[i] = min(dp[i], 1 + dp[i - sq])
    return dp[n]

print(num_squares(12))  # 3: 4+4+4
print(num_squares(13))  # 2: 4+9
print(num_squares(1))   # 1: 1

调试 DP：常见错误

DP 中常见的错误包括：基础情况错误（dp[0] 设置不正确）、填充顺序错误（访问了尚未计算的值）、状态定义中的差一错误（dp[i] 表示 TO（到达 i）的代价，还是表示 LEAVE（离开 i）的代价），以及无穷大仍然存在时没有返回 -1（表示无法完成的情况）。在测试较大的输入之前，请务必先用最简单的情况进行测试（空输入、单个元素、target=0）。

# Common DP debugging checklist:
# 1. Base case: what is dp[0]? dp[1]? Are they correct?
# 2. State definition: write it in English before coding
# 3. Recurrence: trace manually on a 3-element example
# 4. Fill order: dependency arrows point left/up? Fill left/up first
# 5. Infinity check: return -1 or 0 when dp[target] == inf?
# 6. Array bounds: dp has size n+1 for 0..n, or n for 0..n-1?

# Quick test template:
def test_coin_change():
    assert coin_change([1], 0) == 0     # base case
    assert coin_change([1], 1) == 1     # single coin
    assert coin_change([2], 3) == -1    # impossible
    assert coin_change([1,5,6,9], 11) == 2
    print('All tests passed!')

test_coin_change()

快速检查

请测试您对本课程中数据结构 & 算法——编程面试准备相关概念的理解。

课程回顾

本课中您学习了：硬币兑换最少数量 DP（无界背包）以及贪心法失败的原因；使用硬币外层、金额内层顺序来计算组合数的硬币兑换 II；以及同时采用从左到右和从右到左定义方式的最小代价爬楼梯。接下来，我们将探索使用打家劫舍、Kadane 算法和单词拆分的 1D DP 模式。

常见问题解答

「零钱兑换与最低成本爬楼梯」课时是免费的吗？

是的 — 「零钱兑换与最低成本爬楼梯」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

「零钱兑换与最低成本爬楼梯」这节课中我会学到什么？

建立零钱兑换和最低成本爬楼梯的递推式，选择正确的 DP 方向，并手动跟踪表格计算。你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「零钱兑换与最低成本爬楼梯」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 DSA Interview Prep