Pythonで解くコイン両替問題：動的計画法を使った実装方法

はじめに

この記事では、コイン両替（Coin Change）問題をPythonで解く方法について詳しく解説します。動的計画法（Dynamic Programming）を活用することで、全探索よりもはるかに少ない計算量で答えを求めることができます。

問題の定義

額面の異なる複数のコイン（配列 S）と、その各額面が無限に供給される状況を考えます。このとき、目標金額 n を作り出す組み合わせが全部で何通りあるかを求めるのがこの問題です。なお、コインの並び順が違うだけのもの（例：「1枚＋2枚」と「2枚＋1枚」）は、同じ組み合わせとして1通りと数えます。

単純な再帰で解くと同じ部分問題を何度も計算してしまい非効率ですが、動的計画法を使えば結果を表に保存しながらボトムアップで計算できるため、時間計算量を大幅に削減できます。

実装例

# 動的計画法によるアプローチ
def count(S, m, n):
    # ベースケース用にテーブルを初期化
    table = [[0 for x in range(m)] for x in range(n+1)]
    # n=0 の場合（金額0を作る方法は「何も選ばない」1通り）
    for i in range(m):
        table[0][i] = 1
    # 残りの値をボトムアップ方式で埋めていく
    for i in range(1, n+1):
        for j in range(m):
            # S[j] を含む解の数
            x = table[i - S[j]][j] if i-S[j] >= 0 else 0
            # S[j] を含まない解の数
            y = table[i][j-1] if j >= 1 else 0
            # 合計を格納
            table[i][j] = x + y
    return table[n][m-1]

# メイン処理
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print("Number of coins:", end="")
print(count(arr, m, n))

出力結果

Number of coins:6

アルゴリズムのポイント

この実装の核心は、二次元の table を使って次の2つの場合の数を足し合わせている点です。

• x（コインを含む場合）： コイン S[j] を1枚使った残りの金額 i − S[j] を作る方法の数。同じコインを何度でも使えるため、同じ列 j を参照します。
• y（コインを含まない場合）： コイン S[j] を一切使わずに金額 i を作る方法の数。これは直前のコインまでを使う場合の数 table[i][j-1] に相当します。

すべての変数はローカルスコープ内で宣言されており、処理の流れは上記の手順に沿って進みます。最終的に table[n][m-1] に目標金額 n の組み合わせ総数が格納されます。

この例では、コイン [1, 3, 2, 4] を使って金額 5 を作ると、6通りの組み合わせが存在することが確認できます。

まとめ

この記事では、動的計画法を用いてコイン両替問題を解くPythonプログラムの実装方法を学びました。部分問題の答えを表に保存するこの手法は、再帰的な全探索に比べて圧倒的に高速であり、類似のナップサック問題や組み合わせ最適化の問題にも応用できる重要な考え方です。ぜひ自分のコードにも取り入れてみてください。