【JavaScript】最小枚数のコインで指定金額を作る方法｜動的計画法による解説

問題概要

JavaScriptで、第一引数に配列 arr を受け取る関数を実装します。この配列には、利用可能な硬貨の額面（種類）が格納されています。

第二引数には数値 amount を渡します。これは合計したい目標金額を表し、関数はその金額をちょうど作るために必要な最小のコイン枚数を返します。

なお、どうしてもその金額を作れない場合は -1 を返す必要があります。

例えば、次のような入力があったとします。

const arr = [1, 2, 5];
const amount = 17;

この場合の出力は次のようになります。

const output = 4;

出力の解説

17という金額は「5の硬貨3枚」と「2の硬貨1枚」、合計4枚で作ることができるため、答えは4になります。

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

この問題は動的計画法を使うことで効率的に解けます。0から順番に各金額ごとの最小枚数を配列に記録していき、金額 i を作るための最小枚数は「i − コインの額面」の最小枚数に1を加えた値の中で最も小さいもの、として求めます。

サンプルコード

const arr = [1, 2, 5];
const amount = 17;
const minCoins = (arr = [], amount = 1) => {
    const changes = [];
    changes[0] = 0;
    while(changes.length <= amount){
        let change = Math.pow(2, 31) - 1;
        for (let i = 0; i < arr.length; i++) {
            if (changes.length - arr[i] < 0){
                continue;
            };
            change = Math.min(change, 1 + changes[changes.length - arr[i]]);
        };
        changes.push(change);
    };
    return changes[amount] == Math.pow(2, 31) - 1 ? -1 : changes[amount];
};
console.log(minCoins(arr, amount));

出力結果

コンソールには以下のように出力されます。

4

コードのポイント

• 初期化： changes[0] = 0 とすることで、金額0を作るのに必要なコインは0枚だと定義します。
• 大きな初期値： Math.pow(2, 31) - 1 は実質的な「無限大」の代わりとして使われ、まだ到達できない金額を表します。
• 作れない場合の処理： 最終的に amount の位置が初期値のままなら、その金額は組み合わせで作れないため -1 を返します。
• 計算量： 金額 × コインの種類数だけループするため、時間計算量は O(amount × n) となり、全探索よりも大幅に効率化できます。