# **動的計画法（Dynamic Programming, DP）とは？**

動的計画法（DP）は、**「最適部分構造」** と **「部分問題の重複」** という性質を持つ問題を効率的に解くためのアルゴリズム設計手法です。
具体的には、**問題を小さな部分問題に分解し、それらを再利用しながら解を構築する** 方法です。

---

## **動的計画法の基本的な考え方**

DP を使う際には、以下の 3 つのステップを踏むのが一般的です。

1. **状態の定義（`dp[i]` を何とするか）**
2. **遷移式（状態の更新方法）を考える**
3. **初期条件を設定する**
4. **計算順序を考える（小さい問題から順番に解く）**

---

## **DP の適用条件**

動的計画法が適用できる問題には、次の 2 つの特徴があります。

### **① 最適部分構造（Optimal Substructure）**

> **「大きな問題の最適解が、小さな部分問題の最適解を使って表現できる」**

- 例：`dp[i]`（部屋 `i` への最短時間）は、`dp[i-1]` や `dp[i-2]` の値を使って求めることができる。

### **② 部分問題の重複（Overlapping Sub problems）**

> **「同じ部分問題を何度も計算する」**

- 例：`dp[i]` を求めるとき、`dp[i-1]` や `dp[i-2]` を参照するが、`dp[i-1]` も `dp[i-2]` を参照しているため、計算が重複する。

このような場合、**メモ化（配列に値を保存して使い回す）** することで、無駄な計算を省略し、高速化できる。

---

## **DP の分類**

DP にはいくつかの種類があります。よく使われるものを紹介します。

### **① 一次元 DP（配列`dp`を用いる）**

- **例：最短経路、階段の登り方、ナップザック問題**
- **特徴**：
    - `dp[i]` という配列を用意して、ある状態から次の状態へ遷移していく。
    - 線形 (`O(N)`) の計算量で解けることが多い。

**例：今回のダンジョン問題**

```javascript
dp[i] = min(dp[i - 1] + A[i], dp[i - 2] + B[i]);
```

### **② 二次元 DP（`dp[i][j]` のように表を用いる）**

- **例：部分和問題、最長共通部分列（LCS）、動的計画法での迷路探索**
- **特徴**：
    - `dp[i][j]` のような表を使い、2 次元的に状態を管理する。
    - 計算量は `O(N*M)` になることが多い。

**例：最長共通部分列（LCS）**

```javascript
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (文字が一致するか?))
```

### **③ ナップザック DP（制約付き DP）**

- **例：0-1 ナップザック問題**
- **特徴**：
    - ある制約（例：重さ `W` を超えないようにする）を満たしつつ最適解を求める。
    - `dp[i][w]` を使うことが多い。

**例：ナップザック問題**

```javascript
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]);
```

---

## **ダンジョン問題を動的計画法で解く流れ**

### **1. `dp[i]` の定義**

`dp[i]` を「部屋 `i` にたどり着くまでの最短時間」と定義。

### **2. 遷移式を考える**

部屋 `i` へは、以下の 2 つの方法で移動できる：

- **部屋 `i-1` から `i` へ**（時間 `A[i]` ）
- **部屋 `i-2` から `i` へ**（時間 `B[i]` ）

したがって、遷移式は：

```javascript
dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3]);
```

### **3. 初期条件**

- `dp[1] = 0` （スタート地点）
- `dp[2] = A[0]`（部屋 `2` へは `A[2]` で移動）

### **4. 実装**

```javascript
function minTimeToReachRoomN(N, A, B) {
    let dp = new Array(N + 1).fill(Infinity);
    dp[1] = 0;

    for (let i = 2; i <= N; i++) {
        dp[i] = Math.min(dp[i], dp[i - 1] + A[i - 2]);
        if (i > 2) {
            dp[i] = Math.min(dp[i], dp[i - 2] + B[i - 3]);
        }
    }
    return dp[N];
}
```

---

## **動的計画法（DP）のメリット**

✅ **計算の重複を避けて高速化できる**（`O(N)` や `O(N*M)` の計算量）
✅ **最適解を求めるのに向いている**（最短経路や最大値・最小値を求める問題）
✅ **再帰よりも効率的な場合が多い**（特にメモ化なしの再帰は `O(2^N)` の計算量になることが多い）

---

## **まとめ**

- **動的計画法（DP）** は、「部分問題の重複」と「最適部分構造」を利用して問題を効率よく解く手法。
- **ダンジョン問題** では、`dp[i]` を部屋 `i` への最短時間とし、`dp[i-1]` と `dp[i-2]` を使って更新した。
- 計算量 `O(N)` なので、大きな `N` に対しても高速に動作する。

---