Loading...

プレビュー

全49ステップ中15ステップのみ表示

ログインして全て見る

コイン交換

中級

Coin Change

与えられたコインで目標金額を作る最小コイン数を見つけます。

📊 計算量

区分	計算量
最良	O(amount × coins)
平均	O(amount × coins)
最悪	O(amount × coins)
空間	O(amount)

🏷️ Tags

DP1Dテーブル最適化

📖 概念紹介

コイン交換問題は、与えられたコインで目標金額を作るのに必要な最小コイン数を見つけるアルゴリズムです。同じコインを複数回使用できます。

1/49

Loading...

🎯最小コイン数を探す

与えられたコインで目標金額を作ります! • コインの種類: [1, 3, 4]円 • 目標金額: 6円条件: コインの数を最小化! （同じコインを複数回使用可能）

🔒

基礎学習

コイン交換

定義

コイン交換問題は、与えられたコインで目標金額を作るのに必要な最小コイン数を見つけるアルゴリズムです。同じコインを複数回使用できます。

主な特性

✓dp[i] = 金額iを作る最小コイン数
✓時間計算量: O(金額 × コイン種類)
✓usedCoin配列で逆追跡して実際のコイン組み合わせを復元
✓Unbounded Knapsackの特殊ケース

時間計算量

最良

O(amount × coins)

平均

O(amount × coins)

最悪

O(amount × coins)

空間計算量

O(amount)

コイン交換 | AlgoNote