動的計画法（DP）パターン

上級

カテゴリ: dynamic-programming

概要

動的計画法（DP）は、複雑な問題を重複する部分問題に分割し、各部分問題の解を記録して再計算を避けることで効率的に解くアルゴリズム設計手法です。「最適部分構造」と「重複する部分問題」という2つの重要な特性を持つ問題に適用でき、再帰的な解法の非効率性を解消します。ボトムアップ（テーブル）またはトップダウン（メモ化）のアプローチで実装できます。

コードテンプレート

Java

Python

- ボトムアップDP（フィボナッチ数列の例）
int fibonacci(int n) {
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

最適化問題最大値最小値部分問題メモ化テーブル状態遷移重複計算最適部分構造ボトムアップトップダウン漸化式最長部分列最小コスト最大利益組み合わせの数

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
フィボナッチ数列（Fibonacci Number）: n番目のフィボナッチ数を計算する
2
最長増加部分列（Longest Increasing Subsequence）: 配列内の最長の増加する部分列の長さを求める
3
コイン交換問題（Coin Change）: 特定の金額を作るのに必要な最小のコイン数を求める
4
編集距離（Edit Distance）: 2つの文字列間の最小編集距離を計算する

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

中

家泥棒

あなたは専門の泥棒で、一列に並んだ家を襲おうとしています。それぞれの家には特定の金額のお金が保管されており、隣接する家には高度なセキュリティシステムが接続されています。このシステムは、隣接する2つの家...

易

階段登り

あなたは階段を登っています。頂上まで到達するには n 段の階段を登る必要があります。一度に 1 段または 2 段登ることができます。何通りの方法で頂上まで登ることができるかを求める関数を作成してく...

中

コイン交換

異なる種類のコインと目標金額が与えられたとき、目標金額を作るために必要な最小のコイン枚数を計算するアルゴリズムを設計してください。もし目標金額を作ることができない場合は、-1を返してください。...