動的計画法（Dynamic Programming, DP）は、問題に多数の重複する部分問題がある場合に効果的な手法です。DPの各状態は前の状態から導き出されます。これは貪欲法とは異なり、貪欲法は部分的な最適解を選択します。

解法ステップ

• dp配列（またはdpテーブル）とそのインデックスの意味を決定する。
• 再帰式（または推移式）を決定する。
• dp配列の初期化を行う。
• 探索順序を決定する。
• dp配列を例を使って推論する。

再帰式はdp配列の初期化方法を決定する場合もあります。

デバッグ方法

dp配列を出力して、想定通りに推論されているか確認するのが最も良い方法です。

コードを書く前に、dp配列上で状態遷移がどのように行われるかシミュレーションを行い、最終的な結果が想定通りであることを確認します。

509. フィボナッチ数

この問題は簡単な動的計画法の入門問題ですが、基本的な手法論を習得するために重要なステップです。

• dp配列：dp[i]はフィボナッチ数列のi番目の値を表す。
• 再帰式：F(n) = F(n - 1) + F(n - 2)
• 初期化：F(0) = 0, F(1) = 1
• 探索順序：左から右へ
• dp配列の例を使って推論：dp配列を出力し、想定通りであることを確認。

実装

class Fibonacci {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] sequence = new int[n + 1];
        sequence[0] = 0;
        sequence[1] = 1;
        for (int i = 2; i <= n; i++) {
            sequence[i] = sequence[i - 1] + sequence[i - 2];
        }
        return sequence[n];
    }
}

70. 登り方問題

この問題はフィボナッチ数と似ています。

• dp配列：i段目の階段に登る方法の数dp[i]
• 再帰式：dp[i] = dp[i - 1] + dp[i - 2]
• 初期化：dp[1] = 1, dp[2] = 2
• 探索順序：左から右へ
• dp配列の例を使って推論：dp配列を出力し、想定通りであることを確認。

実装

class Staircase {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] ways = new int[n + 1];
        ways[1] = 1;
        ways[2] = 2;
        for (int i = 3; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }
        return ways[n];
    }
}

746. コスト最小化登り方問題

この問題では、最初のステップのコストはかかりません。

• dp配列：i段目の階段に登る最小コストdp[i]
• 再帰式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
• 初期化：dp[0] = 0, dp[1] = 0
• 探索順序：左から右へ
• dp配列の例を使って推論：dp配列を出力し、想定通りであることを確認。

実装

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