Pythonで指定金額を作るために必要な最小コイン枚数を求めるプログラム

異なる額面（1、5、10、25）のコインと合計金額 amount が与えられたとき、その金額をちょうど作るために必要な最少のコイン枚数を計算する関数を定義します。たとえば入力が 64 の場合、出力は 7 になります。これは 25 + 25 + 10 + 1 + 1 + 1 + 1 = 64 という組み合わせで構成できるためです。

解法のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。「dp[i] ＝ 金額 i を作るのに必要な最小コイン枚数」と定義し、小さい金額から順に値を埋めていきます。具体的な手順は以下の通りです。

• amount が 0 の場合は 0 を返す
• コイン配列の最小値が amount より大きい場合は -1 を返す（その金額は作れないため）
• サイズ amount + 1 の配列 dp を定義し、すべて -1 で初期化する（-1 は「まだ作れない」ことを表す）
• コイン配列の各要素 i について以下を繰り返す：
  • i が dp の長さ - 1 より大きい場合はスキップして次の反復へ進む
  • dp[i] := 1 とする（コイン i を 1 枚使えば金額 i が作れるため）
  • 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] を返す

アルゴリズムのポイント

各金額 j に対して、「コイン i を 1 枚追加した場合の残り金額 j - i に必要な枚数 + 1」を候補として比較することで、重複する部分問題を一度だけ計算すれば済みます。これにより全探索に比べて計算量を大幅に抑えられ、時間計算量は O(amount × コインの種類数)、空間計算量は O(amount) となります。

実装例

以下の実装を見ると、より理解しやすくなります。

class Solution(object):
    def coinChange(self, amount):
        coins = [1,5,10,25]
        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(64))

入力

64

出力

7