此贴仅供学习讨论，请勿非法传播
upd: 2025.5.11
* 增加了分组背包部分的题目对比。
0 动态规划的基本概念
0.1 基本思想
动态规划（Dynamic Programming），简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的（如对第i个物品拿或者不拿），这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划的入门思路：dfs暴力 -> 记忆化搜索 -> 递推DP。
0.2 解题步骤
* ① 根据题目所求确定DP数组含义。题目所求即为DP数组含义，所求相关即为DP数组的维度。
* ② 确定答案。根据题目含义和DP数组含义确定最终答案所在。
* ③ 确定状态转移方程。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，通常会根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
* ④ 初始化
* ⑤ 遍历顺序（确定目标）
* ⑥ 打印dp数组（用于debug）
0.3 动态规划特点
0.3.1 最优化原理（最优子结构）
如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
0.3.2 无后效性
即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
例如：计算状态f[2]后，结点a[3]的状态是不会变的，因此只需要加上结点a[3]就是状态f[3]。简单的说，就是在计算后面的数值时，只于当前的数值有关而与之前的数值无关。
0.3.3 子问题重叠
即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
0.3.4 优化
DP的优化一般是对DP方程做等价变形。
1 单序列模型
1.1 基本概念
* 特点：状态通常只与序列的前一个或前几个状态有关。
* DP数组定义：以第i位结尾的xx属性。
* 常见问题：
* 最长上升子序列（LIS） ：给定一个序列，找到最长的严格递增的子序列。
* 最大子数组和：在一个数组中找到一个连续子数组，使其和最大。
* 解码方法：给定一个数字字符串，计算解码方式的总数（如 'A' -> 1，'B' -> 2，...，'Z' -> 26）。
* 状态转移：通常 dp[i] 表示以第 i 个元素结尾的子问题的解。
1.2 例题
1.2.1 最长上升子序列
问题描述
给定一个无序的整数数组，找到最长严格递增子序列的长度。
最长上升子序列_信奥算法普及/提高--ACGO题库
思路
1. 状态定义：dp[i]表示以nums[i]结尾的最长递增子序列长度
2. 答案：dp数组中的最大值
3. 状态转移：对于每个i，遍历j从0到i-1，如果nums[i] > nums[j]，则dp[i]可能等于dp[j]+1
4. 初始化：每个位置的初始长度为1（至少包含自己）
5. 遍历顺序：外层循环1到n，内层循环1到i
代码实现
1.2.2 最长公共子序列
问题描述
最长公共子序列_信奥算法普及/提高--ACGO题库
给定两个字符串序列 X 和 Y，找出它们的最长公共子序列（LCS）的长度。子序列不要求连续，但必须保持相对顺序。
思路
1. 初始化一个二维数组dp，大小为(len(X)+1) x (len(Y)+1)，所有元素初始化为0。
2. 遍历字符串X的每一个字符，对于每个字符，遍历字符串Y的每一个字符：
* 如果X的第i个字符和Y的第j个字符相等，则dp[i][j] = dp[i-1][j-1] + 1。
* 否则，dp[i][j]取dp[i-1][j]和dp[i][j-1]中的较大值。
3. 最终，dp[len(X)][len(Y)]即为所求的最长公共子序列的长度。
代码实现
2 双序列模型
2.1 基本概念
* 特点：涉及两个序列，状态通常与两个序列的前缀有关。
* DP数组定义：以A序列的第i位结尾，以B序列的第j位结尾的xx属性。
* 常见问题：
* 最长公共子序列（LCS） ：给定两个序列，找到它们的最长公共子序列。
* 编辑距离：将一个字符串转换成另一个字符串所需的最少操作次数（插入、删除、替换）。
* 状态转移：通常 dp[i][j] 表示第一个序列的前 i 个元素和第二个序列的前 j 个元素的解。
2.2 例题
2.2.1 最长公共子序列
问题描述
最长公共子序列_信奥算法普及/提高--ACGO题库
给定两个字符串 X 和 Y，要求找出它们的最长公共子序列的长度。子序列是指从原序列中删除一些元素（可以不连续）后剩下的序列，而不改变剩余元素的相对顺序。例如：
* X = "ABCBDAB"，Y = "BDCABA" 的一个 LCS 是 "BCBA"，长度为 4。
思路
最长公共子序列问题是一个经典的动态规划问题。以下是解决该问题的详细思路：
1. 动态规划的定义
我们定义一个二维数组 dp[i][j]，表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。
2. 状态转移方程
* 如果 X[i-1] == Y[j-1]（即当前字符匹配），那么 dp[i][j] = dp[i-1][j-1] + 1。
* 如果 X[i-1] != Y[j-1]（即当前字符不匹配），那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 初始化
* dp[0][j] = 0 和 dp[i][0] = 0，因为空字符串与任何字符串的 LCS 长度为 0。
4. 填充顺序
从 i=1 到 len(X)，j=1 到 len(Y)，依次填充 dp 表。
5. 结果
dp[len(X)][len(Y)] 就是 X 和 Y 的最长公共子序列的长度。
示例演示
以 X = "ABCBDAB"，Y = "BDCABA" 为例：
* 初始化 dp 表为 0。
* 逐步填充 dp 表：
* 当 X[0]='A' 和 Y[0]='B' 不匹配，dp[1][1] = max(dp[0][1], dp[1][0]) = 0。
* 当 X[0]='A' 和 Y[3]='A' 匹配，dp[1][4] = dp[0][3] + 1 = 1。
* 最终 dp[7][6] = 4。
代码实现
2.2.2 编辑距离
问题描述
编辑距离_信奥算法普及/提高--ACGO题库
我们需要计算将字符串 A 转换成字符串 B 所需的最少操作次数。允许的操作有三种：
1. 删除一个字符：从字符串 A 中删除一个字符。
2. 插入一个字符：在字符串 A 中插入一个字符。
3. 替换一个字符：将字符串 A 中的一个字符替换为另一个字符。
思路
这个问题是经典的编辑距离（Edit Distance） 问题，通常使用动态规划（Dynamic Programming, DP）来解决。
动态规划定义
定义 dp[i][j] 为将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最少操作次数。
初始化
* dp[0][j] = j：将空字符串 A 转换为 B 的前 j 个字符，需要进行 j 次插入操作。
* dp[i][0] = i：将 A 的前 i 个字符转换为空字符串 B，需要进行 i 次删除操作。
状态转移方程
对于 dp[i][j]，我们考虑以下情况：
1. A[i-1] == B[j-1] ：当前字符相同，不需要操作，dp[i][j] = dp[i-1][j-1]。
2. A[i-1] != B[j-1] ：需要进行以下三种操作之一，取最小值：
* 插入：dp[i][j-1] + 1（在 A 的前 i 个字符后插入 B[j-1]）
* 删除：dp[i-1][j] + 1（删除 A[i-1]）
* 替换：dp[i-1][j-1] + 1（将 A[i-1] 替换为 B[j-1]）
因此，状态转移方程为：
示例计算
让我们用示例 A = "sfdqxbw", B = "gfdgw" 来计算：
初始化：
* A 的长度 m = 7, B 的长度 n = 5。
* dp[0][j] = j, dp[i][0] = i。
逐步填充 dp 表：
（这里只展示关键步骤）
1. dp[1][1]: A[0]='s', B[0]='g' → 替换，dp[1][1] = dp[0][0] + 1 = 1
2. dp[1][2]: A[0]='s', B[1]='f' → 插入 'f'，dp[1][2] = dp[1][1] + 1 = 2
3. dp[2][1]: A[1]='f', B[0]='g' → 删除 'f'，dp[2][1] = dp[1][1] + 1 = 2
4. dp[2][2]: A[1]='f', B[1]='f' → 相同，dp[2][2] = dp[1][1] = 1
5. 继续填充直到 dp[7][5]。
最终 dp[7][5] 就是答案。
代码实现
3 计数问题
3.1 基本概念
特点：要求统计满足条件的方案数，需注意避免重复计数。
3.2 例题
3.2.1 神奇的魔法币
有若干种魔法币，每种魔法币有固定面值，可以无限使用。支付魔法币时，必须恰好等于愿望的总价值才能实现愿望。求支付的方案数量。
神奇的魔法币_信奥算法普及/提高--ACGO题库
3.2.2 思路
这个问题类似于经典的“完全背包问题”或“硬币找零问题”，其中我们需要计算用无限数量的不同面值的硬币凑出某个金额的总方法数。
对于每一种硬币面值 coin，我们更新 dp 数组：
对于每个金额 i 从 coin 到 m，dp[i] += dp[i - coin]。
这表示：如果我们要凑出金额 i，可以考虑使用一个面值为 coin 的硬币，然后剩下的金额 i - coin 的凑法数就是 dp[i - coin]。因此，dp[i] 增加 dp[i - coin]。
3.2.3 代码实现
4 背包问题
4.1 基本概念
特点：在容量限制下选择物品，状态包含“容量”维度。
4.2 01背包
问题描述
思路
状态转移方程
滚动数组优化
4.3 完全背包
问题描述
思路
状态转移方程
滚动数组优化
4.4 多重背包
问题描述
思路
状态转移方程
二进制优化
4.5 混合背包
问题描述
思路
状态转移方程
二进制优化
4.6 分组背包
4.6.1 问题描述
4.6.2 思路
4.6.3 状态转移方程（朴素版）
分组背包_信奥算法题-ACGO题库
4.6.4 滚动数组优化
4.6.5 例题
4.6.5.1 T46887.通天之分组背包
问题描述
通天之分组背包_信奥算法题-ACGO题库
* 有一个容量为 m 的背包。
* 有 n 个物品，每个物品有自己的重量 a_i、价值 b_i 和所属的组别 c_i。
* 这些物品被分成了 k 组（组别编号从 1 到 k）。
* 每组中的物品是相互冲突的，这意味着在同一组中，你最多只能选择其中一个物品（或者不选）。
* 目标是选择一些物品放入背包，使得总重量不超过 m，且总价值最大。
思路
1. 状态定义：定义 dp[j] 表示背包容量为 j 时能获得的最大价值。
2. 组处理：对于每一组，我们考虑选择组内的哪一个物品（或不选）能最大化 dp[j]。
* 对于每个容量 j，遍历组内的所有物品，检查是否可以将该物品放入背包（即 j >= a_i），并更新 dp[j]。
3. 顺序：通常先遍历组，然后遍历背包容量（从大到小，类似于 01 背包），最后遍历组内的物品。
代码实现
4.6.5.2 T46890.我爱运动鞋
问题描述
我爱运动鞋_信奥算法题-ACGO题库
思路
