网站建设开发设计营销公司山东闵行专业做网站

网站建设开发设计营销公司山东,闵行专业做网站,最火的主题wordpress,平面设计专业学什么目录 前言 一、区间 DP 的核心思想与解题框架 1.1 什么是区间 DP#xff1f; 1.2 区间 DP 的解题四步曲 步骤 1#xff1a;定义状态dp[i][j] 步骤 2#xff1a;推导状态转移方程 步骤 3#xff1a;初始化 DP 表 步骤 4#xff1a;确定填表顺序 1.3 区间 DP 的时间…目录前言一、区间 DP 的核心思想与解题框架1.1 什么是区间 DP1.2 区间 DP 的解题四步曲步骤 1定义状态dp[i][j]步骤 2推导状态转移方程步骤 3初始化 DP 表步骤 4确定填表顺序1.3 区间 DP 的时间复杂度分析二、经典例题实战从理论到代码2.1 例题 1回文字串洛谷 P1435—— 基于端点的区间 DP题目描述解题分析步骤 1状态定义步骤 2状态转移方程步骤 3初始化步骤 4填表顺序C 代码实现代码解释2.2 例题 2Treats for the Cows洛谷 P2858—— 两端选择的区间 DP题目描述解题分析步骤 1状态定义步骤 2状态转移方程步骤 3初始化步骤 4填表顺序C 代码实现代码解释2.3 例题 3石子合并弱化版洛谷 P1775—— 基于分割点的区间 DP题目描述解题分析步骤 1状态定义步骤 2状态转移方程步骤 3初始化步骤 4填表顺序C 代码实现代码解释2.4 例题 4248洛谷 P3146—— 合并相等元素的区间 DP题目描述解题分析步骤 1状态定义步骤 2状态转移方程步骤 3初始化步骤 4填表顺序C 代码实现代码解释三、区间 DP 的常见变形与优化技巧3.1 常见变形1. 环形区间 DP2. 多维约束的区间 DP3. 区间 DP 求方案数3.2 优化技巧1. 前缀和 / 后缀和优化2. 状态压缩3. 四边形不等式优化总结前言在动态规划的大家族中区间 DP 绝对是 看似复杂实则有章可循 的典范。它不像线性 DP 那样按部就班地从左到右递推也不像背包问题那样围绕 选或不选 做文章而是以 区间 为核心通过拆分大区间、求解小区间最终拼凑出全局最优解。如果你曾被 回文串最少插入次数、石子合并最小代价 这类问题难住如果你想掌握一种能解决所有区间相关最优解问题的通用思路那么区间 DP 就是你必须攻克的技能。它的核心思想极其优雅 ——大区间的解依赖于小区间的解就像搭积木一样先搭好小块再用小块拼成大块。本文将从区间 DP 的基本原理出发结合 4 个经典例题回文字串、Treats for the Cows、石子合并、248手把手教你从状态定义到代码实现的完整流程。下面就让我们正式开始吧一、区间 DP 的核心思想与解题框架1.1 什么是区间 DP区间 DPInterval Dynamic Programming是动态规划的一种特殊形式其状态通常以区间的左右端点来定义即dp[i][j]表示区间[i, j]上的最优解最大 / 最小值、方案数等。它的核心逻辑源于分治思想对于一个长度为len j - i 1的大区间[i, j]我们可以通过枚举分割点ki ≤ k j将其拆分为两个小区间[i, k]和[k1, j]然后利用这两个小区间的最优解结合当前区间的约束条件推导出大区间[i, j]的最优解。形象地说区间 DP 就像切蛋糕要吃完一块大蛋糕大区间我们可以先把它切成两块小蛋糕小区间吃完小蛋糕后再把结果整合起来状态转移。1.2 区间 DP 的解题四步曲无论什么区间 DP 问题都可以遵循以下四个核心步骤堪称 万能框架步骤 1定义状态dp[i][j]这是区间 DP 的灵魂必须明确dp[i][j]表示的具体含义。常见的定义有dp[i][j]区间[i, j]变成回文串的最小插入次数回文字串问题dp[i][j]合并区间[i, j]的石子所需的最小代价石子合并问题dp[i][j]取完区间[i, j]的零食能获得的最大收益Treats for the Cows 问题关键原则状态定义必须能覆盖 区间 的核心属性并且让小区间的解能支撑大区间的推导。步骤 2推导状态转移方程这是区间 DP 的核心难点需要根据问题的具体约束分析大区间如何从小区间推导而来。常见的推导方式有两种基于区间端点根据区间左右端点i和j的关系直接推导如回文字串问题中s[i]与s[j]是否相等基于分割点枚举分割点k将区间[i, j]拆分为[i, k]和[k1, j]再整合两者的结果如石子合并问题关键原则转移方程必须保证 无后效性即小区间的解一旦确定就不会被后续操作修改。步骤 3初始化 DP 表由于区间 DP 是从小区间向大区间推导需要先初始化长度为 1 的区间i j因为长度为 1 的区间是最小的单位其解通常是已知的回文字串问题dp[i][i] 0单个字符本身就是回文串无需插入字符石子合并问题dp[i][i] 0单堆石子无需合并代价为 0零食问题dp[i][i] a[i] * n最后一天取这包零食乘数为总天数n步骤 4确定填表顺序区间 DP 的填表顺序非常关键必须保证在计算dp[i][j]时所有依赖的小区间都已经计算完成。最常用的填表顺序是按区间长度len从小到大枚举len从 2 到n对于每个长度len枚举所有可能的左端点i计算右端点j i len - 1确保区间长度为len填充dp[i][j]的值这种顺序能确保当计算长度为len的区间时所有长度小于len的小区间都已经计算完毕完全符合 小区间支撑大区间 的逻辑。1.3 区间 DP 的时间复杂度分析假设问题的序列长度为n则枚举区间长度O(n)len从 1 到n枚举左端点O(n)i从 1 到n - len 1枚举分割点如需O(n)k从i到j-1因此区间 DP 的时间复杂度通常为O(n³)。对于n ≤ 300的问题如石子合并300³ 27,000,000完全在时间限制内对于n ≤ 1000的问题如回文字串1000³ 1e9需要优化但大部分题目会通过约束让n控制在 300 以内。二、经典例题实战从理论到代码2.1 例题 1回文字串洛谷 P1435—— 基于端点的区间 DP题目链接https://www.luogu.com.cn/problem/P1435题目描述任意给定一个字符串通过插入若干字符将其变成回文词求最少需要插入的字符数。注意区分大小写例如Ab3bd需要插入 2 个字符变成回文串。解题分析步骤 1状态定义dp[i][j]将字符串区间[i, j]变成回文串所需的最小插入次数。步骤 2状态转移方程若s[i] s[j]此时[i, j]的回文性由[i1, j-1]决定插入次数与[i1, j-1]相同即dp[i][j] dp[i1][j-1]若s[i] ! s[j]有两种选择在i左侧插入s[j]此时需要先将[i, j-1]变成回文串再插入 1 个字符代价为dp[i][j-1] 1在j右侧插入s[i]此时需要先将[i1, j]变成回文串再插入 1 个字符代价为dp[i1][j] 1取两种选择的最小值即dp[i][j] min(dp[i][j-1], dp[i1][j]) 1步骤 3初始化dp[i][i] 0单个字符无需插入对于i j的非法区间dp[i][j] 0空区间也是回文串。dp表如下所示步骤 4填表顺序按区间长度len从小到大枚举len从 2 到n再枚举左端点i计算右端点j i len - 1。C 代码实现#include iostream #include string #include algorithm using namespace std; const int N 1010; int dp[N][N]; // dp[i][j]表示区间[i,j]变成回文串的最小插入次数 int main() { string s; cin s; int n s.size(); s s; // 字符串从1开始索引方便区间表示 // 初始化长度为1的区间无需插入 for (int i 1; i n; i) { dp[i][i] 0; } // 按区间长度从小到大枚举 for (int len 2; len n; len) { // 枚举左端点i for (int i 1; i len - 1 n; i) { int j i len - 1; // 计算右端点j if (s[i] s[j]) { dp[i][j] dp[i1][j-1]; } else { dp[i][j] min(dp[i][j-1], dp[i1][j]) 1; } } } cout dp[1][n] endl; return 0; }代码解释字符串预处理将原字符串前面加一个空格让索引从 1 开始这样区间[i, j]的表示更直观避免出现i0的边界问题。填表顺序严格按照 长度从小到大 的顺序确保计算dp[i][j]时dp[i1][j-1]、dp[i][j-1]、dp[i1][j]都已计算完成。时间复杂度O(n²)无需枚举分割点仅枚举长度和端点对于n1000的字符串1e6次运算完全可行。2.2 例题 2Treats for the Cows洛谷 P2858—— 两端选择的区间 DP题目链接https://www.luogu.com.cn/problem/P2858题目描述有N份零食排成一列每天可以从两端取一份零食出售。第i份零食的初始价值为V_i如果在第a天出售售价为V_i × a。求所有零食售出后的最大收益。解题分析步骤 1状态定义dp[i][j]取完区间[i, j]的所有零食能获得的最大收益。步骤 2状态转移方程区间[i, j]的长度为len j - i 1已经取了len份零食剩余n - len份零食未取因此当前是第(n - len 1)天因为总天数为n。取零食有两种选择取左端点i收益为V[i] × (n - len 1) dp[i1][j]取当前零食的收益 取剩余区间[i1, j]的最大收益取右端点j收益为V[j] × (n - len 1) dp[i][j-1]取当前零食的收益 取剩余区间[i, j-1]的最大收益取两种选择的最大值即dp[i][j] max(V[i] × cnt dp[i1][j], V[j] × cnt dp[i][j-1])其中cnt n - len 1。步骤 3初始化dp[i][i] V[i] × n长度为 1 的区间最后一天取乘数为n。步骤 4填表顺序按区间长度len从小到大枚举len从 2 到n确保计算dp[i][j]时dp[i1][j]和dp[i][j-1]已计算完成。C 代码实现#include iostream #include algorithm using namespace std; const int N 2010; int dp[N][N]; // dp[i][j]表示取完区间[i,j]零食的最大收益 int V[N]; // 零食的初始价值 int n; // 零食总数 int main() { cin n; for (int i 1; i n; i) { cin V[i]; dp[i][i] V[i] * n; // 初始化最后一天取这包零食 } // 按区间长度从小到大枚举 for (int len 2; len n; len) { int cnt n - len 1; // 当前是第几天取第len包零食 for (int i 1; i len - 1 n; i) { int j i len - 1; // 右端点 // 取左端点或右端点取最大值 dp[i][j] max(V[i] * cnt dp[i1][j], V[j] * cnt dp[i][j-1]); } } cout dp[1][n] endl; return 0; }代码解释天数计算cnt n - len 1是关键推导例如len1时cntn最后一天len2时cntn-1倒数第二天符合 每天取一份 的逻辑。状态转移无需枚举分割点只需考虑两端的选择时间复杂度为O(n²)对于n20004e6次运算完全可控。贪心陷阱本题不能用贪心每次取两端较小的例如序列4,1,5,3贪心会得到 34而区间 DP 能得到 35因为贪心会 鼠目寸光忽略后续更大的收益。2.3 例题 3石子合并弱化版洛谷 P1775—— 基于分割点的区间 DP题目链接https://www.luogu.com.cn/problem/P1775题目描述N堆石子排成一排每次只能合并相邻的两堆合并代价为两堆石子质量之和。求将所有石子合并成一堆的最小代价。解题分析步骤 1状态定义dp[i][j]合并区间[i, j]的所有石子所需的最小代价。步骤 2状态转移方程合并区间[i, j]的最后一步必然是将两个相邻的子区间[i, k]和[k1, j]合并i ≤ k j。此时的代价为合并[i, k]的代价dp[i][k]合并[k1, j]的代价dp[k1][j]合并这两个子区间的代价区间[i, j]的总质量因为合并两堆的代价是它们的质量和因此状态转移方程为dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] sum[i][j])其中sum[i][j]是区间[i, j]的石子总质量为了快速计算我们可以用前缀和数组pre_sum预处理sum[i][j] pre_sum[j] - pre_sum[i-1]。步骤 3初始化dp[i][i] 0单堆石子无需合并其他位置初始化为无穷大0x3f3f3f3f表示初始状态下无法合并。步骤 4填表顺序按区间长度len从小到大枚举len从 2 到n枚举左端点i计算右端点j再枚举分割点ki ≤ k j更新dp[i][j]。C 代码实现#include iostream #include cstring #include algorithm using namespace std; const int N 310; const int INF 0x3f3f3f3f; int dp[N][N]; // dp[i][j]表示合并[i,j]石子的最小代价 int pre_sum[N]; // 前缀和数组pre_sum[i]表示前i堆石子的总质量 int n; // 石子堆数 int main() { cin n; memset(dp, INF, sizeof(dp)); // 初始化所有状态为无穷大 // 输入石子质量并计算前缀和 for (int i 1; i n; i) { int x; cin x; pre_sum[i] pre_sum[i-1] x; dp[i][i] 0; // 单堆石子无需合并 } // 按区间长度从小到大枚举 for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; // 右端点 int sum pre_sum[j] - pre_sum[i-1]; // [i,j]的总质量 // 枚举分割点k for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] sum); } } } cout dp[1][n] endl; return 0; }代码解释前缀和优化sum[i][j]用前缀和计算时间复杂度从O(n)降到O(1)避免重复计算区间和。初始化dp数组初始化为无穷大确保未计算的状态不会影响最终结果只有dp[i][i]设为 0合法状态。时间复杂度O(n³)对于n300300³27e6次运算完全在时间限制内。拓展如果题目是环形石子合并洛谷 P1880可以用 倍增数组 技巧将数组长度翻倍s[in] s[i]然后在2n长度的数组上做区间 DP最后取dp[i][in-1]i1~n的最小值和最大值。2.4 例题 4248洛谷 P3146—— 合并相等元素的区间 DP题目链接https://www.luogu.com.cn/problem/P3146题目描述给定一个包含N个正整数的序列每次可以选择两个相邻且相等的数将它们替换为一个比原数大 1 的数例如两个 7 合并为 8。求最终能生成的最大整数。解题分析步骤 1状态定义dp[i][j]将区间[i, j]合并成一个元素后能得到的最大数值若无法合并成一个元素dp[i][j] 0。步骤 2状态转移方程要将[i, j]合并成一个元素必须存在分割点ki ≤ k j使得[i, k]能合并成一个元素dp[i][k] ! 0[k1, j]能合并成一个元素dp[k1][j] ! 0两个元素相等dp[i][k] dp[k1][j]此时[i, j]能合并成dp[i][k] 1因此状态转移方程为dp[i][j] max(dp[i][j], dp[i][k] 1)满足上述三个条件时步骤 3初始化dp[i][i] a[i]长度为 1 的区间合并后就是自身。步骤 4填表顺序按区间长度len从小到大枚举len从 2 到n确保计算dp[i][j]时所有dp[i][k]和dp[k1][j]都已计算完成。C 代码实现#include iostream #include algorithm #include cstring using namespace std; const int N 255; int dp[N][N]; // dp[i][j]表示区间[i,j]合并成一个元素的最大数值0表示无法合并 int a[N]; // 原始序列 int n; // 序列长度 int max_val; // 记录最终的最大数值 int main() { cin n; memset(dp, 0, sizeof(dp)); max_val 0; // 初始化长度为1的区间 for (int i 1; i n; i) { cin a[i]; dp[i][i] a[i]; max_val max(max_val, a[i]); // 初始最大数值为单个元素的最大值 } // 按区间长度从小到大枚举 for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; // 右端点 // 枚举分割点k for (int k i; k j; k) { // 只有两个子区间都能合并成一个元素且数值相等时才能合并 if (dp[i][k] ! 0 dp[k1][j] ! 0 dp[i][k] dp[k1][j]) { dp[i][j] max(dp[i][j], dp[i][k] 1); max_val max(max_val, dp[i][j]); // 更新最大数值 } } } } cout max_val endl; return 0; }代码解释状态含义dp[i][j] 0表示该区间无法合并成一个元素这是本题的关键约束避免无效合并。最大数值更新由于并非所有区间都能合并成一个元素因此需要用max_val实时记录所有合法dp[i][j]的最大值。三、区间 DP 的常见变形与优化技巧3.1 常见变形1. 环形区间 DP如环形石子合并核心技巧是倍增数组将环形问题转化为线性问题。例如将数组s扩展为s[1..2n]其中s[in] s[i]然后在2n长度的数组上做区间 DP最后取dp[i][in-1]i1~n的最优解。2. 多维约束的区间 DP如区间 DP 结合背包约束此时状态定义会增加维度例如dp[i][j][k]表示区间[i,j]在花费k的情况下的最优解但本质还是遵循 小区间支撑大区间 的逻辑。3. 区间 DP 求方案数如 摆花 问题洛谷 P1077状态定义为dp[i][j]表示前i种花摆j盆的方案数转移方程为dp[i][j] dp[i-1][j-k]k为第i种花的盆数本质是区间 DP 与多重背包的结合。3.2 优化技巧1. 前缀和 / 后缀和优化如石子合并问题中用前缀和快速计算区间和避免重复计算降低时间复杂度。2. 状态压缩对于某些区间 DP 问题状态可以压缩维度。例如当dp[i][j]只依赖于dp[i1][j]和dp[i][j-1]时可以用一维数组压缩但大部分区间 DP 问题需要二维状态。3. 四边形不等式优化对于满足四边形不等式的区间 DP 问题如石子合并可以将时间复杂度从O(n³)优化到O(n²)。核心思想是通过记录最优分割点减少分割点的枚举范围但实现较为复杂适合n较大的场景。总结区间 DP 是动态规划中最具规律性的分支之一它的核心思想 小区间支撑大区间 简单而优雅。无论问题多么复杂只要遵循 定义状态→推导转移方程→初始化→按长度填表 的四步曲就能迎刃而解。本文通过 4 个经典例题详细讲解了区间 DP 的解题流程从基于端点的简单问题到基于分割点的复杂问题覆盖了区间 DP 的主要应用场景。希望大家能通过本文的学习彻底掌握区间 DP在遇到区间类问题时能够游刃有余。最后送给大家一句话动态规划的本质是 记住过去的答案避免重复计算而区间 DP 则是将这句话发挥到了极致 —— 记住所有小区间的答案最终拼凑出大区间的最优解。