動的計画法(DP)は前の状態から次の状態を導き出す手法であり、貪欲法が局所的に最適解を選択するのとは異なります。アルゴリズム学習において、この違いを理解することが重要です。

動的計画法問題を解決するため、以下の5つのステップを確実に理解する必要があります。これら全てをマスターしてこそ、動的計画法を真に理解したと言えます。

1. DP配列（テーブル）と添字の意味を定義する
2. 漸化式（状態遷移式）を確定する
3. DP配列の初期化方法を決定する
4. 走査順序を確定する
5. 具体例でDP配列の推移を検証する

ユニークパス問題

LeetCode 63: ユニークパス IIでは、障害物のあるグリッド上での経路数を求めます。

// 初期化処理（最適化）
for(int col=1; col<=columns && grid[0][col-1]==0; col++) {
    pathCount[1][col] = 1;
}
for(int row=1; row<=rows && grid[row-1][0]==0; row++) {
    pathCount[row][1] = 1;
}

整数分割問題

LeetCode 343: 整数を分割して積を最大化する問題

1. dp[i]：整数iを分割したときの最大積
2. 漸化式：dp[i] = max({dp[i], (i-j)×j, dp[i-j]×j})
   理解：(i-j)×jは単純な2分割、j×dp[i-j]は3つ以上に分割した場合
3. 初期化：dp[2] = 1
4. 走査順序：dp[i]はdp[i-j]に依存するため、前から後ろへ走査

public int maximizeProduct(int n) {
    int[] results = new int[n+1];
    results[2] = 1;
    
    for(int current=3; current<=n; current++) {
        for(int split=1; split<=current-1; split++) {
            results[current] = Math.max(results[current], 
                Math.max(split * (current-split), split * results[current-split]));
        }
    }
    
    return results[n];
}

二分探索木のカウント

LeetCode 96: 異なる二分探索木の数を数える問題

ノード1をルートにする場合、右部分木に2つのノードがあり、これはn=2の場合の構造と同じです。
ノード3をルートにする場合、左部分木に2つのノードがあり、これもn=2の場合と同じです。
ノード2をルートにする場合、左右の部分木にそれぞれ1つのノードがあり、n=1の場合と同じです。

このように重複する部分問題が見つかり、dp[1]とdp[2]からdp[3]を導けることが分かります。

ナップザック問題

0-1ナップザック

容量Wのナップザックに、最大でどれだけの価値を入れられるか（二次元配列版）

各アイテムについて：

• 入れられない場合：前の値をそのまま使用
• 入れられる場合：入れる場合と入れない場合で価値が大きい方を選択

import java.util.Scanner;

public class KnapsackSolver {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        int itemCount = input.nextInt();  // アイテム数
        int capacity = input.nextInt();   // ナップザック容量
        
        int[] weights = new int[itemCount];
        int[] profits = new int[itemCount];
        
        for(int i = 0; i < itemCount; i++) {
            weights[i] = input.nextInt();
        }
        
        for(int i = 0; i < itemCount; i++) {
            profits[i] = input.nextInt();
        }
        
        // dp[i][w]: i番目までのアイテムで容量wのナップザックに入れられる最大価値
        int[][] dp = new int[itemCount][capacity+1];
        
        // 漸化式: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + profits[i])
        // 初期化: 最初の行を設定
        for(int w = weights[0]; w <= capacity; w++) {
            dp[0][w] = profits[0];
        }
        
        // 走査: 前から後ろへ
        for(int item = 1; item < itemCount; item++) {
            for(int w = 1; w <= capacity; w++) {
                if(w < weights[item]) {
                    dp[item][w] = dp[item-1][w];
                } else {
                    dp[item][w] = Math.max(dp[item-1][w], 
                        dp[item-1][w-weights[item]] + profits[item]);
                }
            }
        }
        
        System.out.println(dp[itemCount-1][capacity]);
    }
}

LeetCode 416: 等和部分集合分割問題
2つのグループに分割し、各グループの合計がsum/2になるナップザック問題に帰着

応用問題

LeetCode 1049: 最後の石の重さ II
石を重量が等しい2つのグループに分けることで、衝突後の残りを最小化します。これは0-1ナップザック問題に変換できます。

容量Xのナップザックを満たす方法の数

LeetCode 494: 目標和問題
式の結果がtargetになるように、正数の合計leftと負数の合計rightを考えます。

left + right = sum、right = sum - left
式: left - (sum - left) = target → left = (target + sum)/2

問題は「容量leftのナップザックを満たす組み合わせの数」に変換されます。

LeetCode 474: 0と1の最大個数
文字列配列から、0の個数がm以下、1の個数がn以下となる最大の部分集合を見つけます。

class Solution {
    public int findMaxForm(String[] strings, int maxZeros, int maxOnes) {
        // dp[zeros][ones]: zeros個の0とones個の1を含む最大文字列数
        int[][] dp = new int[maxZeros+1][maxOnes+1];
        
        for(String str : strings) {
            int zeroCount = 0;
            int oneCount = 0;
            
            for(char c : str.toCharArray()) {
                if(c == '0') {
                    zeroCount++;
                } else {
                    oneCount++;
                }
            }
            
            // 逆順走査で重複を防止
            for(int zeros = maxZeros; zeros >= zeroCount; zeros--) {
                for(int ones = maxOnes; ones >= oneCount; ones--) {
                    dp[zeros][ones] = Math.max(dp[zeros][ones], 
                        dp[zeros-zeroCount][ones-oneCount] + 1);
                }
            }
        }
        
        return dp[maxZeros][maxOnes];
    }
}

逆順走査の重要性：
各アイテムを一度だけ使用する0-1ナップザック問題では、逆順走査が必要です。これにより、同じアイテムが複数回使用されることを防ぎます。