C++ 线性动态规划（LINEAR DP）整理
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
[TOC]
一、基本概念
1. 定义：
* 线性 DP 是动态规划的一种形式，其状态转移沿着线性结构（如数组、字符串、序列等）展开，状态通常由一维或二维表示，且每个状态的转移仅依赖于其前驱状态。
2. 核心要素：
* 状态定义：明确 dp[i] 或 dp[i][j] 的含义（如以第 i 个元素结尾的子问题的解）。
* 状态转移方程：描述状态之间的递推关系（如 dp[i] = max(dp[i-1], dp[i-2] + a[i])）。
* 边界条件：初始化初始状态（如 dp[0] = 0）。
3. 特点：
* 时间复杂度通常为 O(n) 或 O(n²)，空间复杂度可优化为 O(1) 或 O(n)。
* 问题具有明显的“阶段”特性，每个阶段的状态仅由前一阶段决定。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、常见优化方法
1. 空间压缩（滚动数组）：
* 当状态转移仅依赖前几个状态时，用固定大小的数组或变量代替完整数组。
* 示例：斐波那契数列 dp[i] = dp[i-1] + dp[i-2] → 只需两个变量 prev 和 curr。
2. 单调队列优化：
* 适用于状态转移为 dp[i] = min/max(dp[j] + cost(j)) 且 j 在滑动窗口内的情况。
* 示例：滑动窗口最大值问题，时间复杂度从 O(n²) 降至 O(n)。
3. 前缀和优化：
* 当状态转移需要累加区间和时，用前缀和数组快速计算。
* 示例：子数组和问题，sum[i:j] = prefix[j] - prefix[i-1]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、常见问题分类与模型
模型 问题示例 状态定义 转移方程 最长递增子序列 (LIS) 求序列中最长的递增子序列长度 dp[i]：以 a[i] 结尾的 LIS 长度 dp[i] = max((dp[i], dp[j] + 1))（j < i 且 a[j] < a[i]） [最长公共子序列 (LCS)](#2、最长公共子序列 (LCS)) 求两个序列的最长公共子序列 dp[i][j]：a[0:i] 和 b[0:j] 的 LCS 长度 dp[i][j] = dp[i-1][j-1] + 1（若 a[i] == b[j]） 背包问题 0-1 背包、完全背包 dp[i][w]：前 i 个物品装入容量 w 的最大价值
dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) 最大子数组和 求连续子数组的最大和 dp[i]：以 a[i] 结尾的最大子数组和 dp[i] = max(a[i], dp[i-1] + a[i]) 编辑距离 字符串的最小编辑次数（增删改） dp[i][j]：将 a[0:i] 转为 b[0:j] 的最小操作数 dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost) 路径计数 网格中从起点到终点的路径数 dp[i][j]：到达 (i, j) 的路径数 dp[i][j]
= dp[i-1][j] + dp[i][j-1]
1、最长递增子序列（LIS）
1.1 题面
<img src="C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20250402192153197.png" alt="image-20250402192153197" style="zoom:50%;" />
1.2 思路
1. 问题分析
最长上升子序列（LIS）要求找到序列中严格递增的子序列的最大长度。关键在于子序列的元素可以非连续，但必须严格递增。
2. 动态规划思路
最优子结构：以某个元素结尾的 LIS 长度，可以通过其前面的更小元素的 LIS 长度推导而来。
状态定义：定义 dp[i] 表示以第 i 个元素结尾的 LIS 长度。
初始状态：每个元素自身构成长度为 1 的子序列，因此 dp[i] 初始化为 1。
状态转移：对于每个元素 a[i]，遍历其前面的所有元素 a[j]（j < i），若 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
1.3 代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2、最长公共子序列 (LCS)
2.1 题面
<img src="C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20250405202710568.png" alt="image-20250405202710568" style="zoom:50%;" />
2.2 思路
1. 问题分析
最长公共子序列（LCS）要求找到两个字符串中顺序一致但不必连续的最长子序列。
2. 动态规划思路
状态定义：dp[i][j] 表示字符串 X 前 i 个字符和字符串 Y 前 j 个字符的 LCS 长度。
状态转移：
* 若 X[i-1] == Y[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1（当前字符匹配，长度加 1）。
* 否则，LCS 的长度继承自以下两种情况的最大值：
* 不包含 X[i-1]：取 dp[i-1][j]（X 的前 i-1 字符与 Y 的前 j 字符的 LCS 长度）。
* 不包含 Y[j-1]：取 dp[i][j-1]（X 的前 i 字符与 Y 的前 j-1 字符的 LCS 长度）。
即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始状态：dp[0][j] 和 dp[i][0] 均为 0（空字符串无公共子序列）。
2.3 代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3、背包问题
（1）题面
（2）思路
（3）代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4、最大子数组和
4.1 题面
<img src="C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20250402201210154.png" alt="image-20250402201210154" style="zoom:50%;" />
4.2 思路
1. 问题本质分析
目标：寻找数组中连续的一段元素，使得它们的和最大。
关键限制：子段必须连续且非空，数组元素包含正负数。
2. 动态规划思路
观察规律：假设我们已经知道以第 i-1 个元素结尾的最大子段和 dp[i-1]，那么以第 i 个元素结尾的最大子段和有两种可能：
1.单独以 a[i] 开头：dp[i] = a[i]。
2.接续前一个子段：dp[i] = dp[i-1] + a[i]。
选择最优解：每一步选择是否将当前元素加入之前的子段时，若之前的子段和是负数，则直接放弃前面的子段，从当前元素重新开始。负数的前缀和会降低后续子段的总和，因此当 dp[i-1] + a[i] < a[i] 时，直接以 a[i] 作为新起点。取两者中较大值，即 dp[i] = max(a[i], dp[i-1] + a[i])。
全局最大值：遍历过程中，不断记录所有 dp[i] 中的最大值。
4.3 代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5、编辑距离
（1）题面
（2）思路
（3）代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6、路径计数
（1）题面
（2）思路
（3）代码实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、总结
* 核心思路：将问题分解为线性阶段，定义状态并找到递推关系。
* 优化关键：根据问题特点选择合适的优化策略（如单调队列、前缀和）。
* 模型扩展：多数问题可抽象为上述模型，需灵活调整状态定义和转移方程。
