Javaで学ぶ「動的計画法」を体系的に理解する（後半）
前半では、一次元DPを中心に「部分問題」「漸化式」「初期条件」という動的計画法の三本柱を整理しました。 後半では、より本格的なテーマとして二次元DP、状態設計、典型問題、そして実務・セキュリティ・パフォーマンスの観点まで踏み込んでいきます。 読者が「DPを使うべき場面」「どう設計するか」を自分で判断できることを目標にします。
二次元DPとは何か（表で考える動的計画法）
二次元DPは、一次元DPを「縦と横の二方向」に拡張したものです。 配列ではなく「表（テーブル）」を使って、問題を解いていきます。
イメージとしては、dp[i][j] のように二つのインデックスを持つ配列を使い、 「i と j に関する部分問題の答え」をそこに保存していく形です。
例えば、文字列に関する問題（最長共通部分列、編集距離など）は、 二つの文字列の長さに応じて二次元の表を作るのが定番です。
例題1：最長共通部分列（LCS）の二次元DP
最長共通部分列（Longest Common Subsequence, LCS）は、二次元DPの代表的な問題です。 二つの文字列 s と t に対して、「順番を保ったまま共通している文字列のうち、最も長いものの長さ」を求めます。
例えば s = "ABCBDAB" t = "BDCAB" のとき、最長共通部分列の長さは 4 になります。
この問題を二次元DPで解くとき、次のように考えます。
dp[i][j] を「s の先頭から i 文字、t の先頭から j 文字を使ったときの LCS の長さ」と定義する。
Javaコードは次のようになります。
public static int lcs(String s, String t) {
int n = s.length();
int m = t.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
深掘り：この二次元DPの設計を分解する
LCS の DP を、設計の観点から丁寧に分解してみます。
まず、部分問題の定義です。 dp[i][j] は「s の i文字目まで」と「t の j文字目まで」を使ったときの LCS の長さです。 ここで重要なのは、「先頭から i 文字」「先頭から j 文字」という形で、 問題を小さくしている点です。
次に、漸化式（状態遷移）です。 s[i-1] と t[j-1] が同じ文字なら、その文字を共通部分列に含めることができます。 その場合、dp[i][j] = dp[i-1][j-1] + 1 になります。
違う文字なら、その文字は共通部分列に含められないので、 「s の i文字目を捨てる」か「t の j文字目を捨てる」かのどちらかを選びます。 その結果として、dp[i][j] = max(dp[i-1][j], dp[i][j-1]) になります。
最後に、初期条件です。 i = 0 または j = 0 のとき、片方の文字列が空なので、LCS の長さは 0 です。 そのため、dp[0][*] = 0、dp[*][0] = 0 となります。
このように、二次元DPでも
部分問題の定義 漸化式（状態遷移） 初期条件
の三つをきちんと設計することが重要です。
例題2：ナップサック問題の二次元DP
ナップサック問題も、二次元DPの代表的な問題です。 重さと価値を持つ複数の品物があり、 「重さの合計が容量を超えないようにしつつ、価値の合計を最大化する」問題です。
ここでは、0/1ナップサック（各品物を「入れるか入れないか」の二択）を扱います。
dp[i][w] を「最初の i 個の品物を使って、重さの合計が w 以下になるように選んだときの最大価値」と定義します。
Javaコードは次のようになります。
public static int knapsack(int[] weights, int[] values, int W) {
int n = weights.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
int weight = weights[i - 1];
int value = values[i - 1];
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i - 1][w]; // 入れない場合
if (w >= weight) {
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight] + value); // 入れる場合
}
}
}
return dp[n][W];
}
深掘り：ナップサックの状態設計
ナップサックの DP は、状態設計の良い練習になります。
dp[i][w] という定義には、次の意味が込められています。
i という軸 「どこまでの品物を見たか」を表す。 1〜i までの品物を使うかどうかを考える。
w という軸 「現在の重さの上限」を表す。 容量 W の中で、今 w まで使ってよい状況を考える。
この二つの軸を組み合わせることで、 「品物の選び方」と「重さの制約」を同時に扱うことができます。
状態設計とは、「何を dp に持たせるか」を決める作業です。 ここが動的計画法の中で最も難しく、最も重要な部分です。
状態設計の考え方を言語化する
動的計画法を体系的に学ぶうえで、 「状態をどう設計するか」を言語化しておくことは非常に大切です。
まず、「問題を小さくしたときに何が変わるか」を考えます。 LCS なら「文字列の長さ」 ナップサックなら「品物の数」と「重さ」
次に、「その変化をインデックスとして表現できるか」を考えます。 LCS なら i と j ナップサックなら i と w
最後に、「そのインデックスに対して、どんな値を保存すると便利か」を考えます。 LCS なら「LCS の長さ」 ナップサックなら「最大価値」
この三段階を意識すると、 「dp[i][j] に何を入れるべきか」が見えやすくなります。
実務での動的計画法の使いどころ
動的計画法は競技プログラミングやアルゴリズム学習でよく登場しますが、 実務でも次のような場面で使われます。
文字列の類似度を測る（編集距離、LCS） ルーティングや経路探索の最適化 リソース配分の最適化（ナップサックに近い問題） キャッシュ戦略やコスト最小化の計算
ただし、実務では「ライブラリや既存アルゴリズムを使う」ことも多く、 動的計画法をゼロから書く場面はそこまで頻繁ではありません。
それでも、DPの考え方を理解していると、 「この処理は同じ計算を何度もしているから、配列に結果を持てば速くなるな」といった発想が自然に出てくるようになります。
セキュリティ・パフォーマンスの観点から見たDP
セキュリティスペシャリストの視点で見ると、 動的計画法は「計算量を制御するための武器」です。
再帰で書いたアルゴリズムが、入力次第で爆発的に遅くなる場合、 動的計画法に書き換えることで、 最悪ケースの計算量をきちんと抑えることができます。
これは、DoS攻撃（サービス妨害）に対する防御にもつながります。 「入力が大きくても、計算量が O(n²) までに抑えられている」と分かっていれば、 システムの負荷を予測しやすくなります。
一方で、DPはメモリを多く使うことがあります。 二次元配列を大きく取りすぎると、メモリ不足やGC負荷の増大につながるため、 「配列のサイズ」「状態の数」を意識することも重要です。
動的計画法を自分のものにするための最後のポイント
動的計画法は、最初は「パターン暗記」に見えがちですが、 本質は次の三つに集約されます。
部分問題をどう定義するか 漸化式（状態遷移）をどう書くか 初期条件をどう置くか
一次元DPでは dp[i] 二次元DPでは dp[i][j] その中身に「何を持たせるか」を考えるのが、状態設計です。
読者がこの三つを意識しながら、 フィボナッチ、階段、LCS、ナップサックなどを自分の手で書いてみると、 動的計画法は「難しいテクニック」から「頼れる道具」に変わっていきます。
もしさらに踏み込みたい場合は、 最長増加部分列（LIS）、編集距離、区間DPなども、次の良いステップになります。