インタラクティブPythonラボ

Coin Change DP

プレイグラウンドはロード時に自動実行されます。コードを実行をクリックして自分の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
で
初
期
化
す
る
(
d
p
[
0
]
=
0
が
正
し
い
)
"
,
"
∞
で
な
く
0
で
d
p
を
初
期
化
す
る
"
]

Practice questions

コインの組み合わせ数を数える(コインチェンジ2)
最大コイン(全額を超えずに最大枚数)

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

チャレンジ

coins=[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...