Pythonで解くコイン両替問題：最小枚数の硬貨で目標金額を作る動的計画法

異なる額面のコインのリストと合計金額 amount が与えられたとき、その金額をちょうど作るために必要な最小のコイン枚数を求める関数を定義します。どの組み合わせでも金額を作ることができない場合は -1 を返します。

例えば、コインが [1, 2, 5]、金額が 11 の場合、出力は 3 となります。これは 5 + 5 + 1 = 11 という3枚の組み合わせで構成できるためです。

解法のアプローチ（動的計画法）

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。手順は以下の通りです。

• 金額が 0 の場合は 0 を返す
• コイン配列の最小値が金額よりも大きい場合は -1 を返す
• サイズが amount + 1 の配列 dp を定義し、すべての要素を -1 で初期化する
• コイン配列の各要素 i について、以下を処理する
  • i が dp 配列の長さ - 1 より大きい場合は、次の反復へスキップする
  • dp[i] := 1 とする
  • j を i + 1 から amount まで繰り返す
    • dp[j - i] が -1 の場合は、次の反復へスキップする
    • そうでなく dp[j] が -1 の場合は、dp[j] := dp[j - i] + 1 とする
    • それ以外の場合は、dp[j] := min(dp[j], dp[j - i] + 1) とする
• 最後に dp[amount] を返す

ここで、dp[j] は「金額 j を作るのに必要な最小枚数」を表し、到達できない場合は -1 のままになります。各コインを順に適用しながら更新していくことで、重複計算を避けつつ最適解を求められます。

実装例

以下のPython実装を見ると、より理解が深まります。

class Solution(object):
    def coinChange(self, coins, amount):
        if amount == 0:
            return 0
        if min(coins) > amount:
            return -1
        dp = [-1 for i in range(0, amount + 1)]
        for i in coins:
            if i > len(dp) - 1:
                continue
            dp[i] = 1
            for j in range(i + 1, amount + 1):
                if dp[j - i] == -1:
                    continue
                elif dp[j] == -1:
                    dp[j] = dp[j - i] + 1
                else:
                    dp[j] = min(dp[j], dp[j - i] + 1)
        return dp[amount]

ob1 = Solution()
print(ob1.coinChange([1, 2, 5], 11))

入力

[1,2,5]
11

出力

3

計算量

時間計算量は O(amount × コインの種類数)、空間計算量は O(amount) です。dp配列の各位置に対してすべてのコインの使用を試みるため、貪欲法とは異なり、コインの額面が不揃いなケースでも確実に最小枚数を求められる点が大きな利点です。