# 动态规划

> 基本思想、解题思路、0-1 背包、完全背包与常见 DP 分类。

## 动态规划

动态规划（Dynamic Programming，简称 DP）是一种在计算机科学和数学中**用来求解最优化问题的方法**（即求最值或统计解的数量）。它通常用于解决那些具有**重叠子问题**（即同一个子问题会被多次求解）和**最优子结构**（即问题的最优解可以通过其子问题的最优解来构造）的问题。

### 基本思想

1. **最优子结构**：如果问题的最优解所包含的子问题的解也是最优的，那么这个问题就具有最优子结构性质。
2. **重叠子问题**：当一个递归算法重复地访问同样的子问题时，这些问题就可以通过动态规划方法来高效解决，避免重复计算。

### 解题思路

1. **确定状态**：首先需要定义状态，即用一组变量来描述问题的关键信息，这些变量的不同取值组合可以表示不同的子问题。
2. **定义状态转移方程**：这是动态规划的核心，描述了如何根据较小的子问题的解来得到更大规模问题的解。
3. **边界条件**：找出问题的基础情况或边界条件，也就是最小规模的子问题，它们可以直接求解而不需要进一步分解。
4. **计算顺序**：按照从小到大的顺序计算出所有子问题的解，通常使用自底向上（从简单子问题开始逐步求解复杂问题）的方式进行。
5. **存储结果**：为了避免重复计算相同子问题，需要将已经解决的子问题的结果存储起来以供后续使用，这通常通过数组或表来实现。

### 背包 DP

#### 0-1 背包问题

已知第 `i` 件物品的重量是 `weight[i - 1]`，价值是 `value[i - 1]`，背包的总容量为 `capacity`。

现要求选若干物品放入背包（**物品只能被选 1 次**），使背包中物品的总价值最大且背包中物品的总重量不超过背包的总容量。

- **状态定义**：设 `dp[i][j]` 表示在前 `i` 个物品中选择一些，装入容量为 `j` 的背包可以获得的最大价值。
- **状态转移方程**：

假设当前已经处理好了前 `i - 1` 个物品的所有状态，那么对于第 `i` 个物品，有两种选择：

case 1: 当第 `i` 个物品不放入背包时，状态转移至 `[i - 1, j]`。可以获得的最大价值为：

```cpp
dp[i][j] = dp[i - 1][j]
```

case 2: 当第 `i` 个物品放入背包时，状态转移至 `[i - 1, j - weight[i - 1]]`。可以获得的最大价值为：

```cpp
dp[i][j] = dp[i - 1][j - weight[i - 1]] + value[i - 1]
```

- **边界条件**：如果没有物品或者背包容量为 0，则最大价值为 0，即 `dp[0][j] = 0` 和 `dp[i][0] = 0`。
- **计算顺序**：从 `i=1, j=1` 开始，按行或列的顺序依次填充表格。
- **存储结果**：最终答案位于 `dp[n][capacity]`，其中 `n` 是物品总数，`capacity` 是背包的最大承重。

::::{tab-set}
:::{tab-item} C++
:sync: cpp

```cpp
int zeroOneKnapsack(vector<int>& weight, vector<int>& value, int capacity) {
    // 创建一个 (n + 1) * (capacity + 1) 的二维数组，行：物品索引，列：容量（包括 0）
    // 第一维通常是物品的数量
    // 第二维表示中间结果的种类数，由于容量不可能为负数，因此中间结果可能是 0...capacity
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    // 边界条件：如果没有物品或者背包容量为 0，则最大价值为 0

    // 状态定义：dp[i][j] 表示在前 i 个物品中选择一些，放入容量为 j 的背包中，可获得的最大价值
    // 根据状态转移方程，填充 dp 数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j - weight[i - 1] >= 0) {
                // 当前物品的重量小于等于背包容量时，可以放，也可以不放
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            } else {
                // 当前物品的重量大于背包容量时，只能选择不放该物品
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][capacity];
}
```

::::

空间优化请参考：<https://www.hello-algo.com/chapter_dynamic_programming/knapsack_problem/#4>

```cpp
int zeroOneKnapsack2(vector<int>& weight, vector<int>& value, int capacity) {
    int n = weight.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = capacity; j >= 1; j--) {
            if (j >= weight[i - 1]) {
                dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
            }
        }
    }

    return dp[capacity];
}
```

#### 完全背包问题

已知第 `i` 件物品的重量是 `weight[i - 1]`，价值是 `value[i - 1]`，背包的总容量为 `capacity`。

现要求选若干物品放入背包（**物品可以无限次使用**），使背包中物品的总价值最大且背包中物品的总重量不超过背包的总容量。

- **状态定义**：`dp[i][j]` 表示在前 `i` 种物品中选择一些，装入容量为 `j` 的背包可以获得的最大价值。
- **状态转移方程**：

在完全背包问题中，每种物品的数量是无限的，因此将物品 `i` 放入背包后，**仍可以从前 `i` 个物品中选择**。

case 1: 当第 `i` 个物品不放入背包时，背包总容量不变，背包中物品的总价值不变。可以获得的最大价值为：

```cpp
dp[i][j] = dp[i - 1][j]
```

case 2: 当第 `i` 个物品放入背包时，状态转移至 `[i, j - weight[i - 1]]`。可以获得的最大价值为：

```cpp
dp[i][j] = dp[i, j - weight[i - 1]] + value[i - 1]
```

- **边界条件**：如果没有物品或者背包容量为 0，则最大价值为 0，即 `dp[0][j] = 0` 和 `dp[i][0] = 0`。
- **计算顺序**：从 `i=1, j=1` 开始，按行或按列的顺序依次填充表格。
- **存储结果**：最终结果存储在 `dp[n][capacity]` 中，其中 `n` 是物品总数，`capacity` 是背包的最大承重。

```cpp
int unboundedKnapsack(vector<int>& weight, vector<int>& value, int capacity) {
    // 创建一个 (n + 1) * (capacity + 1) 的二维数组，行：物品索引，列：容量（包括 0）
    // 第一维通常是物品的数量
    // 第二维表示中间结果的种类数，由于容量不可能为负数，因此中间结果可能是 0...capacity
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    // 边界条件：如果没有物品或者背包容量为 0，则最大价值为 0

    // 状态定义：dp[i][j] 表示在前 i 个物品中选择一些，放入容量为 j 的背包中，可获得的最大价值
    // 根据状态转移方程，填充 dp 数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            if (j - weight[i - 1] >= 0) {
                // 当前物品的重量小于等于背包容量时，可以放，也可以不放
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
            } else {
                // 当前物品的重量大于背包容量时，只能选择不放该物品
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][capacity];
}
```

### 常见 DP 分类

- **划分型 DP**：`dp[i]` 表示前 i 个元素划分后的最优值，枚举最后一段的起点 k 转移，
  如 `dp[i] = min(dp[k] + cost(k+1, i))`。典型问题：分割回文串、单词拆分、划分 k 段的最小最大段和（配合二分答案）。
- **状态机 DP**：状态除下标外还有"当前所处状态"，`dp[i][state]` 按状态机转移，
  常用于买卖股票（持有/不持有）、打家劫舍（偷/不偷）等有状态约束的序列问题，如 `LC122/LC123 买卖股票`。
- **区间 DP**：状态定义为区间 `dp[l][r]`，转移通常枚举区间内的分割点，
  如 `dp[l][r] = min(dp[l][k] + dp[k+1][r]) + cost(l,r)`。典型问题：石子合并、最优矩阵连乘、回文串问题。
- **DAG 上的 DP**：在有向无环图上按拓扑序做动态规划（也可以理解为记忆化搜索），
  如最长路、关键路径。很多“状态之间没有环”的问题都可以建模为 DAG 上的 DP。
- **树形 DP**：状态定义在树节点上，自底向上（后序遍历）汇总子树信息，如树的最大独立集、树的直径、树上背包。
- **状压 DP**：用一个整数的二进制位表示集合状态（每个位代表一个元素是否被选），
  `dp[mask]` 按位转移。适用于 $n$ 较小（一般 $n \le 20$）的集合覆盖、TSP 等问题。
- **数位 DP**：按十进制数位逐位统计满足条件的数字个数，状态记录当前位、前导零、是否贴上限（isLimit）等，
  用于“统计区间 $[L, R]$ 内满足某性质的数的个数”类问题。
- **插头 DP**：在轮廓线上记录插头（连通性）状态的状压 DP，用于棋盘上的连通性问题（如 Hamilton 回路计数）。
- **计数 DP**：以“方案数”为 DP 值，累加所有合法转移（注意取模），如路径计数、划分计数。
- **动态 DP**：用线段树维护矩阵乘法形式的 DP 转移，支持**修改点权后快速重新查询** DP 结果，
  常用于带修改的树上最大权独立集。
- **概率 DP**：状态转移带有概率，DP 值通常是期望或概率，如抛硬币、随机游走的期望步数问题。