C++で学ぶ最大積切り分け問題（DP-36）の解き方

このチュートリアルでは、動的計画法（DP）の定番問題である「最大積切り分け問題（Maximum Product Cutting | DP-36）」を、C++を使って解く方法を詳しく解説します。

この問題では、長さNメートルのロープが1本与えられます。私たちの課題は、このロープを複数の整数の長さに切り分けたとき、各部分の長さの積が最大になるように切ることです。

問題のポイント

例えば、長さ10のロープの場合、3・3・4に切り分けると積は3×3×4=36となり、これが最大値になります。単純に2等分するだけでは最適解にならないため、再帰や動的計画法を用いて全ての切り分け方を効率的に探索する必要があります。

実装例

以下は、再帰を利用して最大積を求めるC++のコードです。オーバーロードされたmax関数で2つまたは3つの整数の最大値を求め、maxProd関数が実際の計算を行います。

#include <iostream>
using namespace std;
// 2つまたは3つの整数の最大値を求める
int max(int a, int b) {
    return (a > b)? a : b;
}
int max(int a, int b, int c) {
    return max(a, max(b, c));
}
// 最大積を返す関数
int maxProd(int n) {
    if (n == 0 || n == 1) return 0;
    int max_val = 0;
    for (int i = 1; i < n; i++)
        max_val = max(max_val, i*(n-i), maxProd(n-i)*i);
    return max_val;
}
int main() {
    cout << "Maximum Product is " << maxProd(10);
    return 0;
}

出力結果

Maximum Product is 36

コードの解説

maxProd関数では、まずベースケースとしてnが0または1の場合に0を返します。その後、iを1からn-1まで変化させながら、「iと(n-i)に切り分けた場合の積」と「さらに(n-i)側を再帰的に切り分けてiを掛けた値」を比較し、最大値を更新していきます。

なお、この再帰的な実装は理解しやすい反面、同じ部分問題を何度も計算するため計算量が大きくなります。実務ではメモ化（memoization）を追加したり、ボトムアップ方式のDPテーブルを用いることで、O(n²)程度まで効率化できます。また、数学的な知見として、可能な限り3で切り分けるのが最適であることも知られています。