Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P3336\":[\"话旧\",771,\"ZJOI2013\"],\"洛谷-P1156\":[\"垃圾陷阱\",18329,null],\"洛谷-P4302\":[\"字符串折叠\",5351,\"SCOI2003\"],\"洛谷-P3698\":[\"小Q的棋盘\",2521,\"CQOI2017\"],\"洛谷-P1757\":[\"通天之分组背包\",28351,null],\"洛谷-P2607\":[\"骑士\",10192,\"ZJOI2008\"],\"洛谷-B3752\":[\"新斐波那契数列\",405,\"信息与未来 2019\"],\"洛谷-B2064\":[\"斐波那契数列\",30580,null],\"洛谷-P4395\":[\"Gem 气垫车\",1748,\"BOI2003\"],\"洛谷-P1040\":[\"加分二叉树\",32166,\"NOIP2003 提高组\"],\"洛谷-P3146\":[\"248 G\",17960,\"USACO16OPEN\"],\"洛谷-P4158\":[\"粉刷匠\",5716,\"SCOI2009\"],\"洛谷-P5322\":[\"排兵布阵\",7294,\"BJOI2019\"],\"洛谷-P1122\":[\"最大子树和\",21734,null],\"洛谷-P5289\":[\"皮配\",874,\"十二省联考 2019\"],\"洛谷-P1880\":[\"石子合并\",61220,\"NOI1995\"],\"洛谷-P2014\":[\"选课\",33994,\"CTSC1997\"],\"洛谷-P1005\":[\"矩阵取数游戏\",35811,\"NOIP2007 提高组\"],\"洛谷-P1049\":[\"装箱问题\",105896,\"NOIP2001 普及组\"],\"洛谷-P1048\":[\"采药\",189977,\"NOIP2005 普及组\"],\"洛谷-P4516\":[\"潜入行动\",3589,\"JSOI2018\"],\"洛谷-P1091\":[\"合唱队形\",66776,\"NOIP2004 提高组\"],\"洛谷-P1095\":[\"守望者的逃离\",38511,\"NOIP2007 普及组\"],\"洛谷-P2585\":[\"三色二叉树\",6392,\"ZJOI2006\"],\"洛谷-P5658\":[\"括号树\",13085,\"CSP-S2019\"],\"洛谷-P2466\":[\"Sue 的小球\",2386,\"SDOI2008\"],\"洛谷-P2501\":[\"数字序列\",2084,\"HAOI2006\"],\"洛谷-P1216\":[\"[IOI1994]数字三角形 Number Triangles\",115003,\"USACO1.5\"],\"洛谷-P3558\":[\"BAJ-Bytecomputer\",2852,\"POI2013\"],\"洛谷-P1855\":[\"榨取kkksc03\",22361,null],\"洛谷-P1616\":[\"疯狂的采药\",87400,null],\"洛谷-P2946\":[\"Cow Frisbee Team S\",5909,\"USACO09MAR\"],\"洛谷-P1617\":[\"爱与愁的一千个伤心的理由\",2525,null],\"洛谷-P4170\":[\"涂色\",18575,\"CQOI2007\"],\"洛谷-P1060\":[\"开心的金明\",90378,\"NOIP2006 普及组\"],\"洛谷-P1063\":[\"能量项链\",45803,\"NOIP2006 提高组\"],\"洛谷-P5020\":[\"货币系统\",28718,\"NOIP2018 提高组\"],\"洛谷-P1020\":[\"导弹拦截\",76670,\"NOIP1999 提高组\"],\"洛谷-P1064\":[\"金明的预算方案\",45100,\"NOIP2006 提高组\"],\"洛谷-P3047\":[\"Nearby Cows G\",6228,\"USACO12FEB\"],\"洛谷-P5301\":[\"宝牌一大堆\",499,\"GXOI/GZOI2019\"],\"洛谷-P1102\":[\"A-B 数对\",91446,null],\"洛谷-P1464\":[\"Function\",65689,null],\"洛谷-P1541\":[\"乌龟棋\",34236,\"NOIP2010 提高组\"],\"洛谷-P2679\":[\"子串\",15587,\"NOIP2015 提高组\"],\"洛谷-P1868\":[\"饥饿的奶牛\",8683,null],\"洛谷-P1273\":[\"有线电视网\",15596,null],\"洛谷-P1352\":[\"没有上司的舞会\",49832,null],\"洛谷-P3177\":[\"树上染色\",8492,\"HAOI2015\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1706767469000,"title":"进阶算法入门(动态规划)","dislikeCnt":0,"content":"# 进阶算法入门(动态规划)\n\n## 动态规划算法思想\n\n动态规划(Dynamic Programming,简称DP)是一种通过拆分问题为子问题并只解决每个子问题一次,将其解决方案保存在一个表格中,从而避免重复计算的算法。动态规划通常用于优化递归问题,以提高算法的效率。\n\n## 记忆化搜索\n\n记忆化搜索是一种优化递归算法的技术,它通过存储已经计算过的子问题的解来避免重复计算,从而提高算法的效率。记忆化搜索通常与递归深度优先搜索结合使用,是动态规划的一种实现方式。\n\n### 基本思想\n\n1. **递归调用**:使用递归来解决问题,将问题拆分为规模较小的子问题。\n2. **记忆数组**:使用一个数组(通常是一维或二维数组)来存储已计算过的子问题的解。\n3. **递归出口**:在每次递归的入口处,首先检查记忆数组中是否已经存在该子问题的解,如果有则直接返回,避免重复计算。\n4. **保存计算结果**:在计算完一个子问题的解后,将其保存到记忆数组中,以备将来使用。\n\n### 例子:斐波那契数列\n\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\nusing namespace std;\n\nconst int MAX_N \u003d 1000;\nvector\u003cint\u003e memo(MAX_N, -1);\n\nint fib(int n) \n{\n if (n \u003c\u003d 1) \n return n;\n\n if (memo[n] !\u003d -1) \n return memo[n];\n\n memo[n] \u003d fib(n - 1) + fib(n - 2);\n return memo[n];\n}\n\nint main() \n{\n int result \u003d fib(5);\n cout \u003c\u003c result \u003c\u003c endl;\n return 0;\n}\n```\n\n在上述例子中,`memo` 数组用于存储计算过的斐波那契数列的值。递归调用 `fib` 函数时,首先检查 `memo` 数组中是否已经有了对应问题的解,如果有直接返回,否则进行递归计算,并将计算结果保存到 `memo` 数组中。\n\n### 优点\n\n1. **避免重复计算**:通过存储子问题的解,避免了重复计算,提高了算法的效率。\n2. **简化递归过程**:将递归过程中的重复计算部分提取出来,简化了递归过程,提高了代码的可读性。\n\n### 注意事项\n\n1. **初始化记忆数组**:在使用记忆化搜索时,需要确保记忆数组的初始化,通常为负值或其他特殊标记。\n2. **合理选择记忆数组的维度**:记忆数组的维度根据问题的特点来选择,一维或二维数组常见,根据问题需要选择合适的形式。\n3. **递归出口的处理**:在递归算法中,一定要正确处理递归出口,以避免死循环。\n4. **不适用于所有问题**:记忆化搜索适用于具有重叠子问题性质的问题,对于某些问题可能并不适用。\n\n### 学习链接\n\n[动态规划(dp)入门 | 这tm才是入门动态规划的正确方式! | dfs记忆化搜索 | 全体起立!!_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1r84y1379W/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 题目练习\n\n[problem:洛谷-B2064],[problem:洛谷-P1464],[problem:洛谷-B3752]\n\n## 线性dp\n\n线性动态规划是一类经典的动态规划问题,通常涉及求解一维数组上的最优解。这类问题包括字串类动态规划和基础类动态规划,其中字串类问题通常涉及求解最长公共子序列(LCS)、最长递增子序列(LIS)等,而基础类问题涉及计数、排列、组合等基本计算。\n\n### 字串类动态规划\n\n#### 最长公共子序列(LCS)\n\n最长公共子序列是求两个序列中最长的共同子序列的长度。假设两个序列为 `str1` 和 `str2`,则状态转移方程为:\n\n$$\n\\begin{equation}\ndp[i][j] \u003d\n\\begin{cases}\n0, \u0026 \\text{if } i \u003d 0 \\text{ or } j \u003d 0, \\\\\ndp[i-1][j-1] + 1, \u0026 \\text{if } \\text{str1}[i-1] \u003d \\text{str2}[j-1], \\\\\n\\max(dp[i-1][j], dp[i][j-1]), \u0026 \\text{otherwise}.\n\\end{cases}\n\\end{equation}\n$$\n其中,`dp[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符的最长公共子序列的长度。\n\n#### 最长递增子序列(LIS)\n\n最长递增子序列是求一个序列中最长的递增子序列的长度。假设序列为 `nums`,则状态转移方程为:$dp[i] \u003d max(dp[i], dp[j] + 1)$ $(nums[i] \u003e nums[j],0 \u003c\u003d j \u003c i) $\n\n其中,`dp[i]` 表示以 `nums[i]` 结尾的最长递增子序列的长度。\n\n### 基础类动态规划\n\n#### 计数问题\n\n计数问题通常涉及在一些限定条件下,计算满足条件的方案数。\n\n##### 爬楼梯问题\n\n爬楼梯问题是求爬上一个楼梯阶梯的方案数,每次可以爬 1 或 2 个阶梯。状态转移方程为:$dp[i] \u003d dp[i-1] + dp[i-2]$\n\n其中,`dp[i]` 表示爬上第 `i` 个阶梯的方案数。\n\n#### 排列问题\n\n排列问题通常涉及在一些限定条件下,计算满足条件的排列数。\n\n#### 不同路径问题\n\n不同路径问题是在一个二维网格中,从左上角到右下角的路径数。每次只能向右或向下移动。状态转移方程为:$dp[i][j] \u003d dp[i-1][j] + dp[i][j-1]$\n\n其中,`dp[i][j]` 表示从左上角到达网格 `(i, j)` 的路径数。\n\n### 学习链接\n\n[动态规划——线性DP_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1a14y1J7Q9/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[线性动态规划 相似题解析 最长上升子序列 最大上升子序列和 最大连续子段和 乘积最大子数组_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1qu4y1t7NW/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 题目练习\n\n[problem:洛谷-P1216],[problem:洛谷-P1020],[problem:洛谷-P1091],[problem:洛谷-P1095],[problem:洛谷-P1541],[problem:洛谷-P1868],[problem:洛谷-P2679],[problem:洛谷-P2501],[problem:洛谷-P3336],[problem:洛谷-P3558],[problem:洛谷-P4158],[problem:洛谷-P5301]\n\n## 背包dp\n\n### 背包问题概述\n\n背包问题是一类经典的动态规划问题,通常涉及在给定容量的背包中选择不同的物品,以使得某个目标值最大或最小。这类问题包括 01背包、多重背包和无限背包,每种类型的背包问题都有不同的特点和解法。\n\n### 01背包问题\n\n01背包问题是最经典的背包问题。其特点是每个物品只能选择一次,即要么放入背包,要么不放。问题的输入通常包括物品的重量和价值,以及背包的容量。目标是选择一些物品放入背包,使得背包中物品的总价值最大。\n\n#### 状态转移方程\n\n设 `dp[i][j]` 表示前 `i` 个物品中,背包容量为 `j` 时的最大总价值。则状态转移方程为:\n\n```\ndp[i][j] \u003d max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])\n```\n\n其中:\n\n- `i` 表示当前考虑的物品编号。\n- `j` 表示当前背包的容量。\n- `w[i]` 表示第 `i` 个物品的重量。\n- `v[i]` 表示第 `i` 个物品的价值。\n\n这个方程的含义是,在考虑第 `i` 个物品时,可以选择放入背包(此时价值为 `dp[i-1][j-w[i]] + v[i]`),也可以选择不放入背包(此时价值为 `dp[i-1][j]`),然后取两者中的最大值。\n\n### 多重背包问题\n\n多重背包问题允许每个物品选择多次,即可以重复放入背包中。问题的输入同样包括物品的重量和价值,以及背包的容量。目标是选择一些物品放入背包,使得背包中物品的总价值最大。\n\n#### 状态转移方程\n\n设 `dp[i][j]` 表示前 `i` 个物品中,背包容量为 `j` 时的最大总价值。则状态转移方程为:\n\n```\ndp[i][j] \u003d max(dp[i-1][j-k*w[i]] + k*v[i]) (0 \u003c\u003d k \u003c\u003d c[i])\n```\n\n其中:\n\n- `i` 表示当前考虑的物品编号。\n- `j` 表示当前背包的容量。\n- `w[i]` 表示第 `i` 个物品的重量。\n- `v[i]` 表示第 `i` 个物品的价值。\n- `c[i]` 表示第 `i` 个物品的最大数量。\n\n这个方程的含义是,在考虑第 `i` 个物品时,可以选择放入背包的数量为 `0` 到 `c[i]`,然后取所有选择中的最大值。\n\n### 无限背包问题\n\n无限背包问题允许每个物品选择无限次,即背包的容量没有限制。问题的输入同样包括物品的重量和价值,以及背包的容量。目标是选择一些物品放入背包,使得背包中物品的总价值最大。\n\n#### 状态转移方程\n\n设 `dp[i][j]` 表示前 `i` 个物品中,背包容量为 `j` 时的最大总价值。则状态转移方程为:\n\n```\ndp[i][j] \u003d max(dp[i-1][j-k*w[i]] + k*v[i]) (0 \u003c\u003d k \u003c\u003d j/w[i])\n```\n\n其中:\n\n- `i` 表示当前考虑的物品编号。\n- `j` 表示当前背包的容量。\n- `w[i]` 表示第 `i` 个物品的重量。\n- `v[i]` 表示第 `i` 个物品的价值。\n\n这个方程的含义是,在考虑第 `i` 个物品时,可以选择放入背包的数量为 `0` 到 `j/w[i]`,然后取所有选择中的最大值。\n\n### 背包问题的优化\n\n在实际问题中,为了优化空间复杂度,可以将二维数组优化为一维数组。具体而言,01背包和多重背包问题可以进行状态压缩,而无限背包问题则无需使用二维数组。\n\n#### 01背包问题的状态压缩\n\n由于状态转移方程中 `dp[i][j]` 仅与上一层 `dp[i-1][j]` 和 `dp[i-1][j-w[i]]` 有关,可以使用一维数组进行状态压缩。即,仅保留当前层和上一层的信息,减少空间复杂度。\n\n```cpp\nvector\u003cint\u003e dp(capacity + 1, 0);\nfor (int i \u003d 1; i \u003c\u003d n; ++i) \n{\n for (int j \u003d capacity; j \u003e\u003d w[i]; --j) \n {\n dp[j] \u003d max(dp[j], dp[j - w[i]] + v[i]);\n }\n}\n```\n\n#### 多重背包问题的状态压缩\n\n多重背包问题同样可以进行状态压缩,通过逆序更新背包容量的方式,减小循环中的计算量。\n\n```cpp\nvector\u003cint\u003e dp(capacity + 1, 0);\nfor (int i \u003d 1; i \u003c\u003d n; ++i) \n{\n for (int j \u003d capacity; j \u003e\u003d w[i]; --j) \n {\n for (int k \u003d 0; k \u003c\u003d c[i] \u0026\u0026 k * w[i] \u003c\u003d j; ++k) \n {\n dp[j] \u003d max(dp[j], dp[j - k * w[i]] + k * v[i]);\n }\n }\n}\n```\n\n### 注意事项\n\n1. **初始化条件:** 在动态规划的过程中,需要特别注意初始化条件,一般情况下将 `dp[0][j]` 和 `dp[i][0]` 初始化为0。\n2. **边界条件处理:** 在处理状态转移方程时,要注意数组越界的情况,确保在数组索引合法的范围内进行操作。\n\n### 学习链接\n\n[【自制】01背包问题算法动画讲解_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1pY4y1J7na/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[0-1背包 完全背包【基础算法精讲 18】_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV16Y411v7Y6/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 练习题目\n\n[problem:洛谷-P1048],[problem:洛谷-P1616],[problem:洛谷-P1855],[problem:洛谷-P1049],[problem:洛谷-P1617],[problem:洛谷-P1102],[problem:洛谷-P1060],[problem:洛谷-P1855],[problem:洛谷-P5020],[problem:洛谷-P1757],[problem:洛谷-P1064],[problem:洛谷-P2946],[problem:洛谷-P1156],[problem:洛谷-P5322],[problem:洛谷-P5289]\n\n## 区间dp\n\n\n区间动态规划是一类解决区间内最优化问题的动态规划方法。这类问题通常需要在给定区间上做出一些决策,以获得最优的结果。区间动态规划可以应用于多种问题,如字符串编辑距离、石子合并、区间内取值等。以下是区间动态规划的详细介绍:\n\n### 区间动态规划的基本思想\n\n区间动态规划的基本思想是将原问题分解为若干个子区间,然后通过子区间的最优解构造出原问题的最优解。在动态规划的过程中,我们通常考虑状态、状态转移方程和边界条件。\n\n### 状态定义\n\n在区间动态规划中,状态的定义通常与问题的性质有关。例如,如果问题涉及到求解某个区间的最小代价、最大得分等,我们可以定义状态为某个区间的最优值。状态通常是一个二维数组,表示区间的起点和终点。\n\n### 状态转移方程\n\n状态转移方程是区间动态规划的核心。它描述了当前区间的最优解如何由前面的状态转移而来。通常,状态转移方程的构建需要考虑当前区间的决策与子区间的关系。区间动态规划的状态转移方程可以分为以下几种情况:\n\n1. **从左到右遍历:** 适用于问题中的决策或计算是从左到右的情况,状态转移方程可能会涉及到前一个状态。\n2. **从右到左遍历:** 适用于问题中的决策或计算是从右到左的情况,状态转移方程可能会涉及到后一个状态。\n3. **跨区间遍历:** 适用于问题中的决策或计算需要跨越一个或多个子区间的情况,状态转移方程可能会涉及到其他区间的状态。\n\n### 边界条件\n\n边界条件是区间动态规划中需要注意的重要问题。通常,我们需要对边界情况进行初始化,确保状态转移方程能够正确地运行。边界条件可能涉及到区间的起点、终点,或者特殊情况的处理。\n\n### 区间动态规划的步骤\n\n1. **定义状态:** 明确问题中状态的含义,定义好二维数组 `dp[i][j]`。\n2. **初始化边界:** 处理边界条件,初始化 `dp[i][i]` 或 `dp[i][i+1]`。\n3. **状态转移方程:** 根据问题的性质,构建状态转移方程,考虑从左到右、从右到左、跨区间等情况。\n4. **计算顺序:** 根据状态转移方程,选择合适的计算顺序,确保前一状态的计算在后一状态之前完成。\n5. **结果返回:** 返回问题所要求的结果,通常是 `dp[0][n-1]`,表示整个区间的最优解。\n\n### 示例:石子合并问题\n\n考虑一个圆形的石子序列,每个石子上有一定的价值。现在要将这些石子合并成一堆,合并过程中,可以选择任意相邻的两堆进行合并,合并的代价为新堆的价值之和。问最终将所有石子合并成一堆的最小代价。\n\n**状态定义:** `dp[i][j]` 表示将区间 `[i, j]` 的石子合并成一堆的最小代价。\n\n**状态转移方程:**\n\n```\ndp[i][j] \u003d min(dp[i][k] + dp[k+1][j] + sum[i][j]) (i \u003c\u003d k \u003c j)\n```\n\n其中,`sum[i][j]` 表示区间 `[i, j]` 的石子总价值,`k` 表示分割点。\n\n**边界条件:** 当 `i \u003d\u003d j` 时,`dp[i][j] \u003d 0`;当 `i + 1 \u003d\u003d j` 时,`dp[i][j] \u003d sum[i][j]`。\n\n**计算顺序:** 从区间长度小到大,从左到右遍历。\n\n**结果返回:** `dp[0][n-1]`,表示整个区间的最小代价。\n\n### 学习链接\n\n[E28【模板】区间DP 石子合并_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1gz4y1y7Rv/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[算法讲解076【必备】区间dp-上_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1NQ4y1b7Uo/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[算法讲解077【必备】区间dp-下_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1du4y1L7gy/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 题目练习\n\n[problem:洛谷-P1880],[problem:洛谷-P3146],[problem:洛谷-P1063],[problem:洛谷-P1005],[problem:洛谷-P4170],[problem:洛谷-P4302],[problem:洛谷-P2466]\n\n## 树形dp\n\n树形 DP(Dynamic Programming)是一种在树结构上进行动态规划的算法。它通常用于解决与树相关的问题,如最长路径、最大权值独立集、最小覆盖等。在树形 DP 中,我们通过递归地处理树的节点,将问题分解为子问题,并通过保存中间结果来避免重复计算。\n\n以下是一些树形 DP 的常见问题和解法,以及一些基本的概念:\n\n### DP状态设计\n\n**状态定义**:定义状态,通常与当前节点及其子树相关。\n\n**状态转移**:根据问题的要求,设计状态之间的转移关系。\n\n### 基本思路\n\n**自底向上**:从叶子节点开始,逐步向上递归计算子树的状态。\n\n**自顶向下**:从根节点开始,递归计算子树的状态。\n\n### 学习链接\n\n[树形 DP:树的直径【基础算法精讲 23】_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV17o4y187h1/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[树形 DP:打家劫舍III【基础算法精讲 24】_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1vu4y1f7dn/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[树形 DP:监控二叉树【基础算法精讲 25】_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1oF411U7qL/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 题目练习\n\n[problem:洛谷-P1352],[problem:洛谷-P1040],[problem:洛谷-P1122],[problem:洛谷-P1273],[problem:洛谷-P2014],[problem:洛谷-P2585],[problem:洛谷-P3047],[problem:洛谷-P3698],[problem:洛谷-P5658],[problem:洛谷-P2607],[problem:洛谷-P3177],[problem:洛谷-P4395],[problem:洛谷-P4516]\n\n","threadId":181203,"likeCnt":1,"createTime":1706767469000,"isWorkbook":true,"viewCnt":301,"openness":2,"fav":false,"id":4545,"trustable":false}