再帰関係の核心概念

再帰関係（または状態遷移方程式）とは、大きな問題をいくつかの部分問題に分解し、それらの部分問題の解を用いて大きな問題の解を導き出すための関係式です。DP配列の各要素は通常、特定の状態における問題の解を表し、再帰関係はこれらの状態間の変換方法を記述します。

再帰関係の特定手順

1. 状態とその変化の分析：
   • 問題の異なる状態を特定し、それらの状態がどのように変換されるかを見つけます。
   • 状態の変化に必要な条件と制約を特定します。
2. 状態遷移方程式の構築：
   • 基本的な部分問題から始めて、それらの間の関係を導き出します。
   • 状態遷移方程式を通じて、ある状態の解を他の状態の解と関連付けます。
3. 初期条件の定義：
   • 初期状態とその対応する解（ベースケース）を明確にします。
   • これらの初期条件が、状態遷移の基礎を提供します。

再帰関係の具体例

例1：フィボナッチ数列

フィボナッチ数列は動的計画法の典型的な問題です。`memo[i]` を i 番目のフィボナッチ数と定義すると、再帰関係は次のようになります：

memo[i] = memo[i-1] + memo[i-2]

初期条件は：

memo[0] = 0, memo[1] = 1

メモ化（キャッシュ）を使用したコード例：

def fib(num, memo={}):
    if num in memo:
        return memo[num]
    if num <= 1:
        return num
    memo[num] = fib(num - 1, memo) + fib(num - 2, memo)
    return memo[num]

print(fib(10))  # 出力：55

例2：ナップサック問題

0-1ナップサック問題では、`dp[i][w]` を i 番目までのアイテムを重さ w のナップサックに入れたときの最大価値と定義します。再帰関係は次のようになります：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + v_i) （ただし w_i <= w の場合）

初期条件は：

dp[0][w] = 0 （すべての w に対して）

コード例：

def knapsack_solver(w_list, v_list, max_w):
    n = len(w_list)
    dp = [[0] * (max_w + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(max_w + 1):
            if w_list[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_list[i-1]] + v_list[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][max_w]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack_solver(weights, values, capacity))  # 出力：7

再帰関係を深く理解するためのポイント

1. DP配列の意味を明確にする： 各DP配列の要素が具体的にどの問題の解を表しているかを明確にします。
2. 状態変化を詳細化する： 状態がどのように一つから別の状態へと変化するか、そしてその変化の過程における条件を理解します。
3. 状態遷移方程式を導出する： 状態間の関係を分析することで、一つまたは複数の既知の状態から現在の状態の解を導き出す方法を明確にします。
4. 再帰関係を検証する： 実際の例や境界条件を通じて、再帰関係の正しさを検証します。