Pythonで指定されたコインのセットから目標金額を作るために必要な最小コイン枚数を求めるプログラム

問題の概要

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

例えば、コインのリストが [1, 2, 5]、金額が 64 の場合、出力は 14 になります。これは「5 を 12 枚 + 2 を 2 枚」＝ 12×5 + 2 + 2 = 64 という組み合わせで実現できるためです。

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

この問題は動的計画法を使うことで効率的に解けます。「dp[i] ＝ 金額 i を作るために必要な最小コイン枚数」と定義し、小さい金額から順に値を埋めていくのが基本的な考え方です。

アルゴリズムの手順

• amount が 0 の場合は 0 を返す
• コイン配列の最小値が amount より大きい場合は -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] を返す

実装例

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],64))

入力

[1,2,5], 64

出力

14

計算量について

この実装では、各コインについて金額 1 から amount まで順に処理するため、時間計算量は O(amount × コインの種類数)、dp 配列の分だけメモリを使用するため空間計算量は O(amount) となります。貪欲法では最適解が保証されないケースがあるため、確実に最小枚数を求めたい場合はこのような DP アプローチが有効です。