C++で解く「コインチェンジ2」— 硬貨の組み合わせ数を動的計画法で求める方法

問題概要

異なる額面の硬貨と合計金額が与えられたとき、その金額をちょうど作れる組み合わせの数を求めるプログラムを作成します。各硬貨は無限に使用できるものとします。

例えば、金額が 5 で硬貨が [1, 2, 5] の場合、組み合わせは次の 4 通りになります。

• (1 + 1 + 1 + 1 + 1)
• (1 + 1 + 1 + 2)
• (1 + 2 + 2)
• (5)

解き方（アルゴリズム）

この問題は動的計画法（DP）を使って効率的に解けます。手順は以下の通りです。

• サイズが amount + 1 の配列 dp を作成する
• dp[0] := 1 と初期化する（金額 0 を作る方法は 1 通りだけ）
• n := coins 配列のサイズとする
• i を 0 から n − 1 まで繰り返す
  • j を coins[i] から amount まで繰り返す
    • dp[j] := dp[j] + dp[j − coins[i]]
• dp[amount] を返す

C++の実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int change(int amount, vector<int>& coins) {
      vector <int> dp(amount + 1);
      dp[0] = 1;
      int n = coins.size();
      for(int i = 0; i < n; i++){
         for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]];
         }
      }
      return dp[amount];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,5};
   cout << (ob.change(5, v));
}

入力

5
[1,2,5]

出力

4

ポイント解説

このアルゴリズムで最も重要なのは、硬貨のループを外側に、金額のループを内側に配置する点です。この順序にすることで、(1 + 2) と (2 + 1) のように順序だけが異なる並びを同じ組み合わせとして扱い、重複カウントを防げます。逆に金額のループを外側にすると、順列（並べ方の違い）まで数えてしまうため注意が必要です。

また、dp[j] は「金額 j を作る組み合わせの総数」を表しており、各硬貨について順に処理することで、dp[j − coins[i]]（その硬貨を 1 枚使った残りの金額の作り方）を加算していきます。

計算量は、時間計算量が O(amount × n)、空間計算量が O(amount) となり、金額や硬貨の種類が増えても効率的に動作します。