动态规划与记忆化搜索

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 ![[00-数据结构与算法笔记/专题总结/动态规划与记忆化搜索#^jk4krx]] ![[00-数据结构与算法笔记/专题总结/动态规划与记忆化搜索#^u6cya8]] ![[00-数据结构与算法笔记/专题总结/动态规划与记忆化搜索#^vi6u2v]] #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 动态规划与记忆化搜索的区别 > ❓动态规划与记忆化搜索的区别是什么？ ^jk4krx 二者都是在 **将 "原问题" 拆分为 "子问题"** 求解的场景下，处理 "**==重叠子问题==**" 的方法，都是通过 "**存储已求得的子问题结果**" 来**避免重复计算**。不同之处在于： - 「记忆化搜索」是在 "**==分治==**" 的求解思想上，通过 "**备忘**" 而对 "**==递归==**" 实现进行优化； - **自顶向下**：从**顶层问题**开始，**通过 "==分治==" 的思想==递归==求解子问题**，并在**每次递归调用时检查和存储子问题的中间结果** - 「动态规划」是通过 "**==迭代/递推==**"的方式求解问题 - **自底向上**：从**最小的子问题**开始，**通过==迭代==逐步解决更大的问题**，直到最终解决整个问题在《算法导论》中提到，"**记忆化搜索**" 本质上即是 "动态规划" 思想的另一种实现方式——**带备忘录的自顶向下递归法**。[^1] 两种方法具有相同的**渐进时间复杂度**，不过在某些情况下，**自顶向下的方式并不需要真正递归地搜索所有子问题（不满足条件时直接跳出），因此可能时间开销更小**。而 dp 的方式，是一定从**最小子问题**开始递推的。 ![[00-数据结构与算法笔记/专题总结/分治与递归#^zoo8sz]] > [!example] 记忆化搜索 + 剪枝可能效率优于 dp > > 参见 [[99-题解/leetcode/lc-2501 数组中最长的方波|lc-2501 数组中最长的方波]] 一题，如果用记忆化搜索，由于是**自顶向下递归**，因此不需要先对数据排序，从哪个入口往下求解都行。但如果是用 dp 的话，就必须先排序，然后**从小到大递推求**。 > > ![[_attachment/00-数据结构与算法笔记/专题总结/动态规划与记忆化搜索.assets/IMG-动态规划与记忆化搜索-6ED456D31D3424F3BA42C4A0082F6185.png|603]] > > [!tip] 对于求**方案数**，**到达目的地的不同路径数**，这类问题 "**记忆化搜索**" 或者 "DP" 都可以 > > - **分治 + 记忆化搜索**： > - `memo[i][j]` 代表从`(i,j)` 到达目的地的不同路径数量，则其等于**经 `(i,j)` 各个邻居到达目的地**的**路径数总和**。 > - **动态规划**： > - `dp[i][j]` 代表从起点到达位置 `(i,j)` 的不同路径数量，则其等于**经 `(i,j)` 各个邻居到达`(i,j)`** 的**路径数总和**。 > # 动态规划（自底向上） ## 动态规划的适应场景 > ❓ 如何判断一个问题是否能应用动态规划求解？ ^u6cya8 动态规划适用于求解 "**具有==最优子结构==性质**" 和 "**具有==重叠子问题==**" 的 **==最优化==问题**。 1. **==最优子结构性质==**："**原问题的最优解**" 可以通过其 "**子问题的最优解**" 来构建得到。 2. **==重叠子问题==**：**不同的子问题之间具有公共的子子问题** "**最优化问题**" 即是指问题**可以有很多可行解**，每个解对应一个值，希望求得的是**具有==最优值==（最大值或最小值）的一个解**（可能有**多个解**能得到**相同的最优值**，只需求得其中一个） #### 最优子结构「**最优子结构**」是一种**性质**：如果**一个问题的最优解可以分解为若干个==子问题的最优解==而构建得到**，则认为**该问题具有最优子结构**， 因而可通过 **==递归地==解决子问题来构建整体问题的最优解**。 > [!faq] ❓ "最优子结构" 与 "状态转移方程" 有什么关联？ > > - 「**最优子结构**」是**关于问题本身的一种性质**，描述了 "**问题的最优解==可以==由子问题的最优解构成**"。 > - 「**状态转移方程**」是**动态规划的具体实现**，描述了 "**==如何==通过子问题的解迭代地推导出更大问题的解**"。 > > 问题具有 "**最优子结构**" 是能够**应用动态规划求解**、描述出 "**==状态转移方程==**" 的前提。 > ^vi6u2v > [!example] 示例：求解 A -> B 之间的最短路径 > > 假设 **A 到 B 一定会经过中间点 C**，则 **A 到 B 的最短路径长度 = A 到 C 的最短路径长度 + C 到 B 的最短路径长度**， > 由此说明 "**求A-> B 之间的最短路径**" 这一问题**具有最优子结构**。 #### 重叠子问题 **不同的子问题在求解过程中会重复出现**，动态规划即是通过**保存这些子问题的解来避免重复计算**。 ## 动态规划方法的核心应用动态规划方法，需要定义/明确 **两个核心要素**： - 「**==状态==**」：表示**问题在某一阶段的==解==**，即**一个子问题的解** - 「**==状态转移方程==**」—— 描述 **==如何==通过已求得的子问题解来==构建==当前问题的解**；此外，还需要确定 "**==边界条件==**" ——即**最小子问题的解**，是应用动态规划进行 **"递推" 所需的起始项**。 ## 应用动态规划求解问题的步骤 > ❓ 如何分析、应用动态规划来具体求解一个最优化问题？ ^4v103k - （1）**判断该问题是否可应用动态规划求解**： 1. ~~是否是求解 "**最优解**" 的问题~~ 2. 问题是否具有 "**最优子结构性质**" ——决定了**是否可以应用动态规划**求解 3. 是否存在 "**重叠子问题**" ——决定了需要 "**备忘/存储**" 多少**子问题状态** - （2）**应用动态规划求解问题**： 1. 定义「**==状态==**」—— 即 `dp[i]` 的定义； - 确定 **填表方向** （如何填 `dp` 表），分析**是否需要额外边界来 "统一/简化" 状态转移逻辑**，从而确定对状态 `dp[i]` 或 `dp[i][j]` 的定义。 2. 定义「**==状态转移方程==**」——即 `dp[i] -> dp[i+1]` 的递推关系式； 3. 确定「**==边界条件==**」—— 最小子问题的解（`dp[0]` 的值），**递推所需的起始项**； 4. 实现 "**自底向上**" 的递推求解过程 #### 判断 dp 填表的方向 > ❓如何判断应用 dp 时填表的方向？ 根据**状态转移方程**来确定：例如： - `dp[i]` 是**由其前面的项 `dp[i-...]`** 还是**由其后面的项 `dp[i+...]`** 求得？ - `dp[i][j]` 是由其**上方、下方、左侧、还是右侧**的项求得？递推过程需要**先求得前一项才能推出后一项**，由此可以确定**填表方向**。 %% ## 动态规划的优化 1. 考虑是否需要开额外边界，从而简化对边界条件的处理逻辑，简化代码； 2. 考虑是否可进行**状态压缩**：应用几个**变量**或者**滚动数组**记录前项。 ### （1）开额外边界开辟额外边界的目的：将**求解「初始项」所需的初始化逻辑** 纳入「 **统一的状态转移方程**」中。如果状态转移方程中涉及 `dp[i-k]` 或者 `dp[i+k]`，则**对于边界情况 `dp[i == 0]` 或 `dp[i == n-1]` 不能应用状态转移方程求解（下标越界）**，需要特别处理。开额外边界即是为了防止越界，而统一对边界条件的处理逻辑，简化代码。 #### 判断是否需要额外边界 > ❓如何判断是否需要为 dp 数组或 dp 表开辟额外的边界？ 如果应用「**状态转移方程**」求解「**初始项 `dp[0]` 或 `dp[1]`**」时 **==超出边界==**（例如需要 `dp[-1]`），则可以 **"==开辟额外边界==" 并 ==重新定义 `dp[i]` 的含义**==。 > [!example] 背包问题 > > - 定义 `dp[i][j]` 表示从**前 `i` 项物品**（下标`[0,i-1]`）中选取物品**放入容量为 `j` 的背包**所能获得的最大价值。 > - `dp` 数组大小为 `(N+1, W+1)`； > - 在**物品维度多开一位**，从而用 `dp[0][.]` 表示不取任何物品的情况，这样对于第一项物品 `nums[0]`，不取的情况可以由 "`dp[0][0]`" 转移得到。 > - `dp[0][.]` 表示 "**==不取任何物品==**" 的情况 > - `dp[.][0]` 表示 "**==背包容量为 `0`==**" 的情况。 > [!example] 打家劫舍问题： > > - 定义 `dp[i]` 表示偷取 `[0, i]` 区间的房子所能获得的最大金额。 > - 状态转移方程：`dp[i] = max(dp[i-1], dp[i-2] + nums[i])` > > 当`i == 0` 和 `i == 1` 时存在越界，因此初始项 `dp[0], dp[1]` 需要单独处理。 > 为此，**==可在 `dp` 数组前部多开两位==**，映射 `dp'[i+2] => dp[i]`，统一实现为： > > - 定义`dp[i+2]` 表示偷取 `[0, i]` 区间的房子所能获得的最大金额 > - `dp` 数组长度为 `n+2` > - 状态转移方程：`dp[i+2] = max(dp[i+1], dp[i] + nums[i])` > - 初始化 `dp[0] = dp[1] = 0`，无特别含义；如何定义 dp： ```cpp // dp[i]表示长为i的s[0, i-1]......, dp[0]表示空,长度为0 vector<int> dp(n + 1, init_val); // dp[i]表示以s[i]结尾的......, vector<int> dp(n, init_val); ``` --- 似乎**并没有完全省略初始化**，例如 [[99-题解/leetcode/lc-494 目标和|lc-494 目标和]] 中，如果不额外开一位，需要单调地初始化第一行第一列。 ### （2）状态压缩 > [!tip] > 应用状态压缩时（利用**变量**或**滚动数组**），初始**变量值**或**滚动数组值**可以自然地设置为 "**==额外边界==**"， > 从而**省略对初始项的初始化逻辑**，统一纳入 "**状态转移**" 的代码逻辑中求得。 ## 动态规划的应用 trick ##### （1）为 dp 数组申请额外空间，处理边界条件 - **多申请一行或一列的空间, 用来处理边界条件** => 可省略对`dp[][]` 首行首列的单独初始化, 简化代码。 => 需要注意循环时的 idx 需要适应地修改, 多出了一行一列。 =》多申请一行一列后，再将二维 dp 压缩成一行后，需要注意每次按行遍历时，首项的初始化； - 多申请额外空间，再通过 "**下标映射**" 来实现对边界条件的处理； > [!example] 示例： [[99-题解/leetcode/lc-198 打家劫舍|lc-198 打家劫舍]] > > 递推关系式为 `dp[i] = max(dp[i-2] + arr[i], dp[i-1])`，正常来说需要**从 `i>=2` 开始递推**，原因在于： > > （1）上述递推式**只在 `i>=2` 成立**； > （2）需保证否则 `i-2` **下标不越界**； > > 在处理时，可**为 dp 数组多开两位** 并进行 **==下标映射==**：**将 `i-2` 映射为=> `i` 从而保证不越界，故取`bias = 2`**， > 由此得到映射后递推式 `dp[i+bias] = max(dp[i-2+bias] + arr[i], dp[i-1]+bias)`， > 即`dp[i+2] = max(dp[i] + arr[i], dp[i+1])` => > > 由此，记 **==`dp[i+2]` 表示偷窃 `[0, i]` 所能获得的最大利润==**，而 **`dp[0]` 与 `dp[1]` 则为边界情况，可根据场景均初始化为 0**。 > > 最后结果返回 `dp[n+1]` 即表示偷窃 `[0, n]` 所能获得的最大利润。 --- %% %% 1. 一维 `dp[]` 的状态转移，可考虑用一个或多个变量来实现。例如 f (n) 只与 f (n-1) 和 f (n-2) 有关, 则可以只用三个变量实现。二维 `dp[][]` 的状态转移，可考虑只用一行数组来实现（滚动数组）。 => 多行压缩成一行后，每一行第一列可以需要根据条件单独处理； %% # 动态规划问题分类 ## 背包问题 > 背包类问题的核心："**选**" 或者 "**不选**" 的思想。 ![[_attachment/00-数据结构与算法笔记/专题总结/动态规划与记忆化搜索.assets/IMG-动态规划与记忆化搜索-54F6F721E991EE3D53F89FFE491B265A.png|621]] ![[Excalidraw-Solution/动态规划与记忆化搜索.excalidraw.svg|419]] %%[[Excalidraw-Solution/动态规划与记忆化搜索.excalidraw.md|🖋 Edit in Excalidraw]]%% ### 0-1 背包问题给定 `N` 个物品（每种物品 **==只有一个==**），每个物品 `i` 具有两个属性：**重量 `weight[i]`** 和 **价值`value[i]`**。求一个容量为 `W` 的**背包所能装下的最大物品价值**。 ### 完全背包问题给定 `N` 种物品（**每种物品有==无限个==**），每个物品 `i` 具有两个属性：**重量 `weight[i]`** 和 **价值`value[i]`**。求一个容量为 `W` 的**背包所能装下的最大物品价值**。 ### 多重背包问题给定 `N` 种物品（**每种==物品的数量由 `cnt[i]` 给定==**），每个物品 `i` 具有两个属性：**重量 `weight[i]`** 和 **价值`value[i]`**。求一个容量为 `W` 的**背包所能装下的最大物品价值**。 ### 分组背包问题 **物品分为 `N` 组**，**==每一组中有若干种不同物品==**，要求**只能从每一组中选择一个物品**。每个物品 `i` 具有两个属性：**重量 `weight[i]`** 和 **价值`value[i]`**。求一个容量为 `W` 的**背包所能装下的最大物品价值**。 %% ## 线性 DP ## 区间 DP ## 树形 DP %% # 参考资料 # Footnotes [^1]: 《算法导论》P207