交互式Python实验室

Coin Change DP

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

mastery 路径

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

解释

Line 1

coin_change([1,5,6,9], 11) called. Find min coins for amount=11.

为什么用这种方法？

We want the fewest coins from [1,5,6,9] that sum to 11. Greedy fails here: 9+1+1=3, but 6+5=2 coins is optimal.

Structured Explanation

Overview

硬币找零: 用给定面值的硬币凑出目标金额的最少硬币数。

Analogy

就像自动售货机用最少数量的硬币找零。

Step-by-step

初始化dp[0]=0，dp[1..amount]=∞
对每个amount遍历所有硬币
dp[i]=min(dp[i],dp[i-coin]+1)
dp[amount]是答案(∞则不可能)

Visual

coins=[1,2,5] amount=11 dp=[0,1,1,2,2,1,2,2,3,3,2,3] dp[11]=3 → (5+5+1)

Common mistakes

[
"
初
始
化
d
p
[
0
]
=
1
(
应
为
0
)
"
,
"
用
0
而
非
∞
初
始
化
d
p
"
]

Practice questions

统计硬币组合数(硬币找零II)
最多硬币(不超过总金额的最大枚数)

Time

O(amount × 硬币数)

Space

O(amount)

复杂度

时间

O(amount × coins)

空间

O(amount)

复杂度概览

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

用硬币=[1,5,6,9]凑成amount=11需要的最少硬币数。逐步构建dp数组。

提示

dp[0]=0, 其余dp[i]=无穷大。对每个硬币c: dp[i] = min(dp[i], dp[i-c]+1) 若i>=c。

代码工作室

Coin Change DP

Monaco就绪

Python就绪

lesson.pyline 1

Loading editor...

输出控制台

1 lines

❯ 2

现实世界应用

1

Currency exchange

2

Vending machines

3

Game power-ups

4

Resource decomposition

Comments

Loading comments...