動的計画法を学ぶために、まずは2つの問題から始めましょう。

1. 鋼板の切断問題

1.1 問題の提示

ある企業は長さがnの鋼板をいくつかの断片に切り分けて販売したいと考えています。市場では、長さi（0[r_n = \max_{1\leq i\leq n}( p_i + r_{n-i}) ]よって、この問題を解決するには「トップダウン」の再帰的な方法が利用できます。

1.3 トップダウン再帰実装

public static int cutRod(int[] prices, int length) {
    if (length == 0) {
        return 0;
    }
    int maxValue = Integer.MIN_VALUE;
    for (int i = 1; i <= length && i <= prices.length; i++) {
        maxValue = Integer.max(maxValue, prices[i - 1] + cutRod(prices, length - i));
    }
    return maxValue;
}

テスト結果から、鋼板の長さが30程度になると処理時間が大幅に増加することが確認できます。これは、多くの再帰呼び出しが繰り返されているためです。例えば、cutRod(prices, n)を計算する際にはcutRod(prices, 0 ~ n-1)を再帰的に求めますが、cutRod(prices, n-1)を計算する際にまた同じ範囲の呼び出しが行われます。このように、一度の計算でn-2回の重複呼び出しが発生し、計算時間は指数関数的に増加します。

木構造で表すと以下のようになります（例：n=4の場合）：

長さnの鋼板に対する実行時間T(n)は以下の再帰式で表現できます：

[T(n) = 1+ \sum_{i=0}^{n-1}T(i) ]数学的帰納法によりT(n) = 2^nであることが導けます。つまり、nが増えるにつれて計算量が急激に増加する理由が分かります。

1.4 トップダウン再帰の改善版実装

上記コードでは多くの重複計算が発生しているため、一度求めた結果をメモ化して再利用することで効率を向上させます。

以下は改善後のコードです：

private static int[] memoTable;

public static int memoizedCutRod(int[] prices, int length) {
    memoTable = memoTable == null ? new int[length + 1] : memoTable;
    if (length == 0) {
        return 0;
    }
    if (memoTable[length] > 0) {
        return memoTable[length];
    }
    int maxValue = Integer.MIN_VALUE;
    for (int i = 1; i <= length && i <= prices.length; i++) {
        maxValue = Integer.max(maxValue, prices[i - 1] + memoizedCutRod(prices, length - i));
    }
    memoTable[length] = maxValue;
    return maxValue;
}

この改良版では、計算時間の大幅な改善が見られます。

さらに、各長さにおける最適分割方法を記録する「解の追跡用配列」を用いると、長さ1〜nまでの最適切断方法を簡単に導き出すことができます。

以下はn=10の場合の例です：

1.5 ボトムアップ実装

上記のトップダウン方式では、全体の問題から小さなサブ問題へと再帰的に分解していきます。しかし、各問題はそれ以前のサブ問題の解に依存しているため、サブ問題を先に解いておくことで効率を上げることができます。

以下はボトムアップ方式による実装です：

public static int bottomUpCutRod(int[] prices, int length) {
    int[] dp = new int[length + 1];
    dp[0] = 0;
    for (int i = 1; i <= length; i++) {
        int maxValue = Integer.MIN_VALUE;
        for (int j = 1; j <= i && j <= prices.length; j++) {
            maxValue = Integer.max(maxValue, prices[j - 1] + dp[i - j]);
        }
        dp[i] = maxValue;
    }
    return dp[length];
}

このコードでは、再帰呼び出しを二重ループで置き換えています。外側のループは問題の規模を管理し、内側のループは現在の問題を解きます。各問題の解は、既に前段階で求めたサブ問題の解（dp配列に保存）から得られるため、直接参照可能です。

1.6 時間計算量の解析

備忘録なしの再帰呼び出しの時間計算量は\(2^n\)であり、メモ化されたボトムアップ方式は\(n^2\)です。これは等差数列の和として求められます。トップダウンとボトムアップの違いは、問題を解く順序のみであり、実質的な計算量はほぼ同じです（ただし、再帰呼び出しはスタックの使用により空間計算量が大きくなります）。

次回は行列積の連結問題を通じて、動的計画法についてさらに深く考察します。