DP核心：再帰＋メモ化

🔥 Vibe プロンプト

「再帰的フィボナッチをDPテーブル方式に変換し、完全なdp配列を出力。各ステップを説明。」

動的計画法とは？

動的計画法（DP） は、複雑な問題を重複する部分問題に分解し、各部分問題を1回だけ解いて結果を再利用する方法です。

| アプローチ | 方向 | メモリ | 速度 | |-----------|------|--------|------| | トップダウン（メモ化） | n → 0 | O(n) コールスタック | O(n) | | ボトムアップ（テーブル） | 0 → n | O(n) 配列 | O(n) |

フィボナッチ：3つの実装

from functools import lru_cache

# 1. トップダウン（メモ化）
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

print(f"fib_memo(50) = {fib_memo(50)}")  # 12586269025

# 2. ボトムアップ（テーブル）
def fib_tab(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp

fib_table = fib_tab(10)
print(f"fib_tab(10) = {fib_table}")
print(f"fib(10) = {fib_table[10]}")

# 3. 空間最適化 — O(1)メモリ
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(f"fib_opt(50) = {fib_opt(50)}")

DP 3ステップ法

| ステップ | 質問 | フィボナッチの場合 | |---------|------|----------------| | 1. 状態定義 | dp[i]は何を表す？ | dp[i] = i番目のフィボナッチ数 | | 2. 漸化式 | dp[i]とdp[i-1]の関係？ | dp[i] = dp[i-1] + dp[i-2] | | 3. 初期条件 | ベースケースは？ | dp[0] = 0, dp[1] = 1 |

他の問題への適用

最大部分配列（Kadaneのアルゴリズム）： | ステップ | Kadane | |---------|--------| | 状態 | dp[i] = 位置iで終わる最大和 | | 漸化式 | dp[i] = max(arr[i], dp[i-1] + arr[i]) | | 初期 | dp[0] = arr[0] |

def max_subarray(arr):
    dp = [0] * len(arr)
    dp[0] = arr[0]
    for i in range(1, len(arr)):
        dp[i] = max(arr[i], dp[i-1] + arr[i])
    return max(dp)

print(f"最大部分配列: {max_subarray([-2,1,-3,4,-1,2,1,-5,4])}")  # 6

計算量比較

| 問題 | DPなし | DPあり | 改善 | |------|--------|--------|------| | フィボナッチ(n) | O(2ⁿ) | O(n) | 指数→線形 | | 最大部分配列(n) | O(n²) | O(n) | 二次→線形 | | ナップサック(n,W) | O(2ⁿ) | O(nW) | 指数→疑似多項式 | | LCS(n,m) | O(2ⁿ⁺ᵐ) | O(nm) | 指数→二次 |

まとめ

| 項目 | 要点 | |------|------| | メモ化 | トップダウン再帰＋キャッシュ | | テーブル化 | ボトムアップ反復＋配列 | | 状態定義 | 最も重要なステップ | | 漸化式 | 部分問題を結ぶ核心の式 | | ベースケース | 漸化式の基礎 | | 空間最適化 | しばしば O(n) → O(1) に削減可能 |