C++で整数ブレーク問題を解く：分割後の積を最大化する動的計画法

正の整数 n が与えられたとき、それを少なくとも2つ以上の正の整数の和に分割し、それらの整数の積が最大になるようにします。求めたいのは、そのとき得られる最大の積です。

例として n = 10 の場合を考えてみましょう。10 = 3 + 3 + 4 と分割すると、3 × 3 × 4 = 36 となり、これが最大値となります。したがって答えは 36 です。

解法のアプローチ

この問題は、メモ化再帰（トップダウンDP）を使うことで効率的に解けます。手順は以下の通りです。

• solve() メソッドを定義する。引数は n、配列 dp、フラグ flag
• n が 0 の場合は 1 を返す
• dp[n] が -1 でない場合は、計算済みなので dp[n] を返す（メモ化）
• flag が立っている場合は end = n - 1、そうでなければ end = n とする
• ret = 0 で初期化する
• i を 1 から end までループさせる
  • ret = max(ret, i * solve(n - i, dp, false)) で最大値を更新
• dp[n] = ret を設定して返す
• main 関数からは、サイズ n + 1 の配列 dp を作成し、すべて -1 で初期化する
• solve(n, dp) の結果を返す

flag の役割について

ここでポイントになるのが flag の存在です。最初の呼び出しでは end = n - 1 となり、「元の数をそのまま使わず、必ず一度は分割する」という制約を実現しています。これにより「少なくとも2つ以上の数に分ける」という条件が満たされます。以降の再帰呼び出しでは false が渡されるため、自由に分割できるようになります。

C++での実装例

以下に実装コードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(int n, vector<int>& dp, bool flag = true){
      if(n == 0) return 1;
      if(dp[n] != -1) return dp[n];
      int end = flag ? n - 1 : n;
      int ret = 0;
      for(int i = 1; i <= end; i++){
         ret = max(ret, i * solve(n - i, dp, false));
      }
      return dp[n] = ret;
   }
   int integerBreak(int n) {
      vector<int> dp(n + 1, -1);
      return solve(n, dp);
   }
};
int main(){
   Solution ob;
   cout << (ob.integerBreak(10));
}

入力

10

出力

36

計算量の目安

各 n について最大 n 回の分割を試すため、時間計算量は O(n²) です。また、メモ化用の配列と再帰スタックにより、空間計算量は O(n) となります。

まとめ

整数ブレーク問題は、「数を分割して積を最大化する」という一見シンプルながら奥深い動的計画法の典型例です。メモ化によって重複する部分問題の計算を省くことで、指数的な探索を多項式時間に抑えられる点が大きな魅力です。類題として「最大積の組み合わせを実際に列挙する」「貪欲法や数学的性質（3を優先的に使う）を利用した解法」などにも挑戦してみると理解がさらに深まります。