動的計画法（DP）とは

動的計画法（Dynamic Programming, DP）は、問題をより小さな部分問題に分割し、その結果を再利用することで効率的に解く手法です。特に「重複部分問題」と「最適部分構造」を持つ問題に有効です。

DPの一般的な手順

1. 状態の定義：DPテーブル（dp配列）の各インデックスが何を表すかを決める。これがすべての基盤となる。
2. 状態遷移式：dp[i]を求めるための漸化式を導く。これが最も難しい部分。
3. 初期化：dp[0], dp[1]などを問題に応じて設定。
4. 計算順序：通常は左→右または右→左。
5. 戻り値：最終的に必要な値（dp[n]とは限らない）。

以下、具体例を通じて理解を深めましょう。

例題1：第N項のテトラナッチ数

テトラナッチ数列は T₀=0, T₁=1, T₂=1 で定義され、n≧0 のとき T_{n+3} = T_n + T_{n+1} + T_{n+2} です。整数 n が与えられたとき、T_n を求めます。

解法（DP）

1. 状態定義：dp[i] = 第i項のテトラナッチ数
2. 遷移式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
3. 初期化：dp[0]=0, dp[1]=1, dp[2]=1
4. 計算順序：左から右へ
5. 戻り値：dp[n]

コード例

public class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

空間最適化（ローリング配列）

変数3つで状態を保持し、空間計算量をO(1)にできます。

public class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0, b = 1, c = 1, d = 0;
        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
}

（参考：LeetCode問題「Three Steps Problem」も同様の考え方で解けます。dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD とします。）

例題2：最小コストで階段を上る

各段にコストが与えられており、1段または2段ずつ進めます。頂上（配列の最後の次の位置）に到達する最小コストを求めます。

解法A（到着時点での最小コスト）

1. 状態定義：dp[i] = 位置iに到達するための最小コスト（iのコストは含まない）
2. 遷移式：dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])
3. 初期化：dp[0]=0, dp[1]=0
4. 計算順序：左→右
5. 戻り値：dp[n]

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = 0; dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2],
                             dp[i - 1] + cost[i - 1]);
        }
        return dp[n];
    }
}

解法B（出発時点からの最小コスト）

1. 状態定義：dp[i] = 位置iから頂上に到達するための最小コスト（iのコストを含む）
2. 遷移式：dp[i] = cost[i] + min(dp[i+1], dp[i+2])
3. 初期化：dp[n-1]=cost[n-1], dp[n-2]=cost[n-2]
4. 計算順序：右→左
5. 戻り値：min(dp[0], dp[1])

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for (int i = n - 3; i >= 0; i--) {
            dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
        }
        return Math.min(dp[0], dp[1]);
    }
}

例題3：デコード方法

数字のみの文字列が与えられます。'A'→1, 'B'→2, ... 'Z'→26 のマッピングで、何通りのデコード方法があるかを求めます。

解法

1. 状態定義：dp[i] = 文字列の先頭からi文字目（0-indexed）までのデコード方法の総数
2. 遷移式：2つのケースを考慮
   • 現在の文字が'1'～'9'なら単独デコード可能 → dp[i] += dp[i-1]
   • 前の文字との組み合わせが'10'～'26'なら2桁デコード可能 → dp[i] += dp[i-2]
3. 初期化：dp[0] = (s[0] != '0') ? 1 : 0 ; 1文字目が'0'なら0。2文字目以降はループ内で処理するため、dp[1]も同様に初期化。
4. 計算順序：左→右
5. 戻り値：dp[n-1]

コード例（初期化を明示）

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        int[] dp = new int[n];
        if (ch[0] != '0') dp[0] = 1;
        if (n == 1) return dp[0];
        // 2文字目
        if (ch[1] != '0' && ch[0] != '0') dp[1] += 1;
        int val = (ch[0] - '0') * 10 + (ch[1] - '0');
        if (val >= 10 && val <= 26) dp[1] += 1;
        for (int i = 2; i < n; i++) {
            if (ch[i] != '0') dp[i] += dp[i - 1];
            int v = (ch[i - 1] - '0') * 10 + (ch[i] - '0');
            if (v >= 10 && v <= 26) dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
}

最適化（ダミー要素を先頭に追加）

dp配列の長さを n+1 にし、dp[0] = 1 とすることで、境界条件の処理を簡略化できます。

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (ch[0] != '0') dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (ch[i - 1] != '0') dp[i] += dp[i - 1];
            int v = (ch[i - 2] - '0') * 10 + (ch[i - 1] - '0');
            if (v >= 10 && v <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
}