動的計画法の基本フレームワーク

動的計画法は過去の計算結果を再利用し、重複計算を回避する手法です。計算結果は通常1次元または2次元の配列に格納されます。実装には以下の3ステップが不可欠です。

ステップ1: 状態の定義

配列memo[i]の意味を明確に定義します。例えばmemo[i]が「i段目までの階段を登る方法の総数」を表す場合、最終的にmemo[n]が求める解となります。

ステップ2: 状態遷移式の導出

小規模問題の解から大規模問題を導出する関係式を確立します。例えばmemo[n] = memo[n-1] + memo[n-2]のように、既存の計算結果を組み合わせて新しい値を算出します。

ステップ3: 基本ケースの設定

再帰的計算の起点となる初期値を設定します。例えばmemo[0] = 0、memo[1] = 1のように、これ以上分解できない最小単位の解を明示的に定義します。

実践例: 階段登り問題

1回で1段または2段登れるカエルがn段の階段を登る場合の経路数を求める問題です。

実装手順

1. 状態定義: steps[i] = i段目までの登り方の総数
2. 遷移式: steps[i] = steps[i-1] + steps[i-2]
3. 初期値: steps[0] = 0, steps[1] = 1, steps[2] = 2

最適化実装

int countWays(int totalSteps) {
    if (totalSteps <= 1) return totalSteps;
    
    int[] steps = new int[totalSteps + 1];
    steps[1] = 1;
    steps[2] = 2;
    
    for (int i = 3; i <= totalSteps; i++) {
        steps[i] = steps[i-1] + steps[i-2];
    }
    return steps[totalSteps];
}

グリッド経路探索問題

m×nグリッドの左上から右下へ移動する経路数を求める問題です。移動は右または下方向のみ許可されます。

状態遷移のポイント

• gridPaths[i][j]: (i,j) に到達する経路数
• 遷移式: gridPaths[i][j] = gridPaths[i-1][j] + gridPaths[i][j-1]
• 境界条件: 最上段と最左列はすべて1（直線経路のみ）

実装コード

int calculatePaths(int rows, int cols) {
    if (rows == 0 || cols == 0) return 0;
    
    int[][] grid = new int[rows][cols];
    
    // 境界条件の初期化
    for (int i = 0; i < rows; i++) grid[i][0] = 1;
    for (int j = 0; j < cols; j++) grid[0][j] = 1;
    
    // 状態遷移の実行
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            grid[i][j] = grid[i-1][j] + grid[i][j-1];
        }
    }
    return grid[rows-1][cols-1];
}

編集距離の計算

2つの文字列を変換する最小操作回数を求める問題です。操作は挿入・削除・置換の3種類です。

状態定義の特徴

editDist[i][j]は、word1の先頭i文字とword2の先頭j文字を一致させる最小操作数を表します。

遷移ロジック

• 文字が一致: editDist[i][j] = editDist[i-1][j-1]
• 不一致時: editDist[i][j] = min(editDist[i-1][j], editDist[i][j-1], editDist[i-1][j-1]) + 1

効率的な実装

int computeEditDistance(String a, String b) {
    int lenA = a.length();
    int lenB = b.length();
    int[][] dist = new int[lenA + 1][lenB + 1];
    
    // 初期化処理
    for (int i = 0; i <= lenA; i++) dist[i][0] = i;
    for (int j = 0; j <= lenB; j++) dist[0][j] = j;
    
    // 状態遷移の計算
    for (int i = 1; i <= lenA; i++) {
        for (int j = 1; j <= lenB; j++) {
            if (a.charAt(i-1) == b.charAt(j-1)) {
                dist[i][j] = dist[i-1][j-1];
            } else {
                dist[i][j] = Math.min(dist[i-1][j], 
                         Math.min(dist[i][j-1], dist[i-1][j-1])) + 1;
            }
        }
    }
    return dist[lenA][lenB];
}

0-1ナップサック問題

容量制限のあるバッグに価値と重さが異なる品物を詰め込む最適化問題です。

動的計画法の適用

maxValue[i][w]を「i個目の品物まで考慮し、容量wで達成可能な最大価値」と定義します。

遷移式の特徴

• 品物を追加しない場合: maxValue[i][w] = maxValue[i-1][w]
• 品物を追加する場合: maxValue[i][w] = maxValue[i-1][w-weight[i]] + value[i]

実装例

int solveKnapsack(int capacity, int[] weights, int[] values) {
    int items = weights.length;
    int[][] dp = new int[items + 1][capacity + 1];
    
    for (int i = 1; i <= items; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i-1] > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = Math.max(
                    dp[i-1][w], 
                    dp[i-1][w - weights[i-1]] + values[i-1]
                );
            }
        }
    }
    return dp[items][capacity];
}