JavaScriptで整数を分割して積を最大化する方法【動的計画法で解く】

問題の概要

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

この関数の役割は、受け取った整数を少なくとも2つの部分に分割することです。分割後の各部分の合計は元の整数 num と一致し、かつ各部分を掛け合わせた積が最大になるようにします。最終的に、関数はこの最大の積を返します。

例として、関数への入力が次の場合を考えてみましょう。

const num = 10;

このとき、期待される出力は以下の通りです。

const output = 36;

出力の解説

10 は「3 + 3 + 4」に分解できます。これらを掛け合わせると 3 × 3 × 4 = 36 となり、これが最大の積です。

他の分割方法と比較してみると分かりやすくなります。たとえば「2 + 8」なら 2 × 8 = 16、「5 + 5」なら 25 となり、どれも 36 には届きません。このことから、できるだけ均等に近く、しかも小さな部分(特に3)に分割するほど積が大きくなるという性質が読み取れます。

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

この問題は動的計画法を使うことで効率的に解けます。dp[i] を「整数 i を分割したときに得られる最大の積」と定義します。

重要なポイントは、各部分に対して「さらに分割した場合の値(dp[j])」と「そのまま使った場合の値(j)」の大きい方を選ぶことです。こうすることで、小さい問題の最適解から順に積み上げて、全体の最適解を求められます。

実装例

コードは次のようになります。

const num = 10;
const breakInt = (num = 2) => {
    const dp = new Array(num + 1).fill(0);
    dp[0] = 0;
    dp[1] = 1;
    for(let i = 2; i <= num; i++){
        for(let j = 1; 2*j <= i; j++){
            dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i-j,
            dp[i-j]) );
        };
    };
    return dp[num];
};
console.log(breakInt(num));

出力結果

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

36

コードの解説

処理の流れを順番に見ていきましょう。

1. DPテーブルの初期化:長さ num + 1 の配列を作り、すべて 0 で埋めます。dp[1] は便宜上 1 としておきます。

2. 外側のループ:i を 2 から num まで順に増やしながら、それぞれの整数に対する最大の積を求めていきます。

3. 内側のループ:j は最初の分割位置を表します。2*j <= i という条件により、対称的な組み合わせの重複計算を防ぎ、計算量を半分に抑えています。

4. 状態遷移:Math.max(j, dp[j]) * Math.max(i-j, dp[i-j]) によって、「j をそのまま使うか、さらに分割するか」「残りの i−j をそのまま使うか、さらに分割するか」の4通りのうち最良の組み合わせを選びます。

計算量

時間計算量は O(n²)、空間計算量は O(n) です。n がそこまで大きくなければ十分実用的な速度で動作します。