動的計画法（メモ化と表作成）とは何か？

Question

動的計画法（メモ化と表作成）とは何か？

Accepted Answer

**動的計画法（DP）**は、**重複する部分問題**と**最適部分構造**を持つ問題を、各部分問題を一度計算して結果を再利用することで解きます。2つのスタイルは、**メモ化**（トップダウン）と**表作成**（ボトムアップ）です。

## 基本的な考え方

素朴な再帰は同じ部分問題を指数時間で再計算します。DPはそれらをキャッシュし、指数時間の処理を多項式時間に圧縮します。

## メモ化（トップダウン）

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## 表作成（ボトムアップ）

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## メモ化vs表作成

| | メモ化 | 表作成 |
|---|------|------|
| 方向 | トップダウン再帰 | ボトムアップ反復 |
| 計算 | 必要な状態のみ | すべての状態 |
| リスク | スタックオーバーフロー | なし |
| 空間 | 削減可能 | しばしばO(1)行に削減可能 |

## 計算量

フィボナッチ：素朴なO(2ⁿ)から**O(n)**時間、O(n)（またはO(1)）空間。

## 使用場面と落とし穴

部分問題が**重複**する場合はDPを使います。状態と漸化式を慎重に定義してください — これが難しい部分です。部分問題が重複しない場合は、通常のdivide-and-conquerで十分です。

## なぜ重要なのか

DPは最短経路、編集距離、ナップサック問題といった手に負えない指数時間問題を効率的な問題に変換します。

状態と漸化式を識別するスキルは、アルゴリズムインタビューで最も重視される能力の一つです。

これはdiffツールから生物情報学の配列アラインメントまで、実システムの基盤となっています。

	メモ化	表作成
方向	トップダウン再帰	ボトムアップ反復
計算	必要な状態のみ	すべての状態
リスク	スタックオーバーフロー	なし
空間	削減可能	しばしばO(1)行に削減可能