JavaScriptで合計がnになる最小個数の完全平方数を動的計画法で求める方法

問題の概要

正の整数 num を唯一の引数として受け取るJavaScript関数を記述する必要があります。

この関数の目的は、合計が入力値と一致するような完全平方数(平方数)の組み合わせを見つけることです。ただし、使用する完全平方数の個数はできるだけ少なくしなければなりません。

例

入力が以下の場合:

const num = 123;

出力は次のようになります:

const output = 3;

これは 123 = 121 + 1 + 1 と表せるためです。121は11の二乗なので、3つの完全平方数で123を構成できています。

アプローチ:動的計画法(DP)

これは古典的な動的計画法(Dynamic Programming)の問題であり、ある数に対する答えを、それより小さい数の結果をもとにして導き出すことができます。

コードに進む前に、まず全体的なパターンと、DPがどのように解法の構築に役立つのかを理解しておきましょう。

小さい数についての結果は次のようになります:

1 --> 1 (1)
2 --> 2 (1 + 1)
3 --> 3 (1 + 1 + 1)
4 --> 1 (4)
5 --> 2 (4 + 1)
6 --> 3 (4 + 1 + 1)

このパターンから、後続の数の結果を求めるには、先行する数の結果どうしの組み合わせを試す必要があることが明らかです。

実装例

以下がそのコードです:

const num = 123;
const sumSquares = (num) => {
    let arr = new Array(num + 1).fill(0);
    arr[1] = 1;
    for(let i = 1; i * i <= num; i++) {
        for(let j = i * i; j < arr.length; j++) {
            if(arr[j] == 0) {
                arr[j] = arr[j - (i * i)] + 1;
            } else {
                arr[j] = Math.min(arr[j - (i * i)] + 1, arr[j]);
            }
        }
    };
    return arr[num];
};
console.log(sumSquares(num));

コードの仕組み

このアルゴリズムでは、配列 arr の各インデックスに「その数を構成するために必要な最小の完全平方数の個数」を順番に格納していきます。

外側のループで候補となる各平方数 i * i を生成し、内側のループでそれを使って更新できる位置 j を走査します。arr[j - (i * i)] + 1(残りの部分の最適解に1を加えた値)と既存の値を Math.min で比較することで、より良い解が見つかるたびに配列を更新していきます。

すべての候補平方数について処理が完了した時点で、arr[num] には入力値を構成する最小個数が格納されているため、それを返せば答えとなります。

出力

コンソールへの出力は次のとおりです:

3