核心原理与实战应用)
1. 区间DP的本质与适用场景区间动态规划Interval DP是动态规划算法中一个极具特色的分支它专门处理那些需要将问题分解为连续子区间进行求解的场景。与常规线性DP不同区间DP的核心在于区间划分的思想——通过枚举所有可能的区间分割点将大问题拆解为相互关联的子问题。1.1 什么情况下应该选择区间DP当问题满足以下三个特征时区间DP往往是最佳选择问题可分解为连续子区间如字符串的子串、数组的连续子序列、时间段的连续区间等子问题具有重叠性不同区间的计算会重复使用相同子问题的解满足最优子结构大区间的最优解能由其包含的小区间最优解组合得到典型应用场景包括矩阵链乘法的最优计算顺序回文子序列/子串相关问题石子合并类的最优代价问题括号匹配的最大长度计算多边形三角剖分的最小得分提示区间DP的时间复杂度通常为O(n³)因为需要枚举区间起点、终点和分割点。当n500时可能需要优化或考虑其他算法。1.2 区间DP与线性DP的本质区别以经典的背包问题线性DP和石子合并问题区间DP对比特征线性DP区间DP状态定义dp[i]表示前i个元素dp[i][j]表示区间i到j转移方向单向递推前→后区间长度递增短→长子问题关系相邻状态依赖任意子区间组合依赖典型问题背包、LIS矩阵链乘、回文分割这种二维状态的设计使得区间DP能精确捕捉子区间之间的复杂关系但也带来了更高的空间复杂度。2. 区间DP的标准解题框架2.1 状态设计的黄金法则区间DP的状态定义通常遵循固定模式dp[i][j] 表示区间[i,j]的最优解或某种性质例如石子合并dp[i][j]表示合并第i到第j堆石子的最小代价最长回文子序列dp[i][j]表示子串s[i..j]的最长回文子序列长度关键点在于区间端点i,j必须明确包含解的范围状态值要能通过更小区间的状态组合得到通常需要配合前缀和等辅助数组进行计算2.2 三重循环的模板结构区间DP的标准实现包含三个嵌套循环# 初始化 n len(data) dp [[0]*n for _ in range(n)] # 枚举区间长度 for length in range(2, n1): # 枚举区间起点 for i in range(n - length 1): j i length - 1 # 计算终点 dp[i][j] INF # 初始化为极大值 # 枚举分割点 for k in range(i, j): # 状态转移方程 dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost(i,j,k))这个模板的精妙之处在于外层按区间长度递增计算确保子问题先于父问题求解中层控制区间滑动窗口的位置内层尝试所有可能的分割方案2.3 边界条件处理技巧边界处理是区间DP最容易出错的部分常见处理方式单元素区间通常dp[i][i]有明确初值for i in range(n): dp[i][i] 0 # 或根据问题设定其他初值相邻元素区间有些问题需要单独初始化for i in range(n-1): dp[i][i1] data[i] data[i1] # 如石子合并无效区间ij时通常设为0或Noneif i j: dp[i][j] 03. 经典问题实战解析3.1 石子合并问题问题描述有N堆石子排成一列每次只能合并相邻的两堆代价为两堆石子数量之和。求将所有石子合并为一堆的最小总代价。状态转移方程推导dp[i][j] min(dp[i][k] dp[k1][j]) sum[i][j], for k in [i,j-1]其中sum[i][j]表示第i到第j堆石子的总数可以用前缀和数组快速计算。完整实现def stoneMerge(stones): n len(stones) prefix [0]*(n1) for i in range(n): prefix[i1] prefix[i] stones[i] dp [[0]*n for _ in range(n)] for length in range(2, n1): for i in range(n-length1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): cost prefix[j1] - prefix[i] dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost) return dp[0][n-1]复杂度分析时间复杂度O(n³) 三重循环空间复杂度O(n²) DP表存储3.2 最长回文子序列问题描述给定字符串s求其最长回文子序列的长度子序列不要求连续。关键观察如果s[i]s[j]则dp[i][j] dp[i1][j-1] 2否则dp[i][j] max(dp[i1][j], dp[i][j-1])实现代码def longestPalindromeSubseq(s): n len(s) dp [[0]*n for _ in range(n)] for i in range(n-1, -1, -1): # 逆序枚举起点 dp[i][i] 1 for j in range(i1, n): if s[i] s[j]: dp[i][j] dp[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1]) return dp[0][n-1]注意事项这里采用逆序枚举i的技巧确保子问题先求解当ij时单个字符本身就是长度为1的回文空间复杂度可优化到O(n)使用滚动数组4. 区间DP的优化技巧4.1 四边形不等式优化对于某些满足单调性的区间DP问题可以将O(n³)优化到O(n²)。核心思想是利用决策单调性减少内层循环次数。适用条件代价函数满足四边形不等式状态转移方程形如dp[i][j] min(dp[i][k] dp[k1][j]) w(i,j)优化后的模板# 记录最优分割点 pos [[0]*n for _ in range(n)] for length in range(2, n1): for i in range(n-length1): j i length - 1 # 缩小k的枚举范围 start pos[i][j-1] if length 2 else i end pos[i1][j] if length 2 else j-1 dp[i][j] float(inf) for k in range(start, end1): if dp[i][k] dp[k1][j] w(i,j) dp[i][j]: dp[i][j] dp[i][k] dp[k1][j] w(i,j) pos[i][j] k4.2 记忆化搜索实现对于边界条件复杂的问题可以采用记忆化搜索递归缓存的方式实现更符合直觉。from functools import lru_cache def intervalDP(s): n len(s) lru_cache(maxsizeNone) def dfs(i, j): if i j: return 0 if i j: return 1 if s[i] s[j]: return dfs(i1, j-1) 2 return max(dfs(i1, j), dfs(i, j-1)) return dfs(0, n-1)优缺点比较优点代码直观边界处理简单缺点递归深度受限可能栈溢出常数时间较大5. 高频面试题精讲5.1 戳气球问题LeetCode 312题有n个气球每个气球标有数字。戳破气球i可以获得nums[i-1]*nums[i]*nums[i1]的硬币。求能获得的最大硬币数。关键思路逆向思考考虑最后戳破的气球kdp[i][j]表示戳破(i,j)区间内所有气球能获得的最大硬币数状态方程dp[i][j] max(dp[i][k] dp[k][j] nums[i]*nums[k]*nums[j]) for k in (i,j)实现代码def maxCoins(nums): nums [1] nums [1] n len(nums) dp [[0]*n for _ in range(n)] for length in range(2, n): for i in range(n-length): j i length for k in range(i1, j): dp[i][j] max(dp[i][j], dp[i][k] dp[k][j] nums[i]*nums[k]*nums[j]) return dp[0][n-1]5.2 多边形三角剖分LeetCode 1039题将凸多边形剖分成若干个三角形每个三角形的得分为三个顶点值的乘积求最小总得分。解法分析将多边形顶点按顺序编号为0到n-1dp[i][j]表示顶点i到j构成的多边形的最小得分枚举中间顶点k形成三角形(i,k,j)状态转移dp[i][j] min(dp[i][k] dp[k][j] values[i]*values[j]*values[k]) for k in range(i1, j)实现要点需要处理环形结构通常固定一条边作为基准初始化所有相邻两点dp[i][i1]06. 区间DP的常见陷阱与调试技巧6.1 易错点排查清单区间端点定义不清确认dp[i][j]是包含还是排除端点检查循环边界是否漏算或多算初始化不完整忘记初始化length1或length2的情况边界条件如ij未处理分割点枚举不全k的范围是否覆盖所有可能分割是否漏掉某些特殊分割情况状态转移条件错误合并代价计算是否正确是否考虑了所有可能的转移路径6.2 调试方法论小规模测试用n3,4的简单案例手动验证打印每个length的完整dp表可视化工具def print_dp(dp): for row in dp: print( .join(f{x:3d} if x!float(inf) else inf for x in row)) print()对比暴力法对小规模数据编写暴力递归解法交叉验证DP结果的正确性断点检查在关键转移步骤添加断言assert dp[i][k] dp[k1][j] cost 0, fInvalid at {i},{j},{k}7. 从模板到变式思维拓展训练7.1 环形区间问题处理对于环形排列的问题如环形石子合并常用解决方法是将原始数组复制一份接在后面长度2n对扩展后的数组进行常规区间DP最终结果为所有dp[i][in-1]中的最优解示例代码def circularStoneMerge(stones): n len(stones) extended stones stones prefix [0]*(2*n1) for i in range(2*n): prefix[i1] prefix[i] extended[i] dp [[0]*(2*n) for _ in range(2*n)] for length in range(2, n1): for i in range(2*n-length1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): cost prefix[j1] - prefix[i] dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost) return min(dp[i][in-1] for i in range(n))7.2 高维区间DP拓展某些问题可能需要更高维的状态表示如加入状态参数dp[i][j][k]表示区间i到j在某种状态k下的最优解例子带颜色标记的石子合并、考虑剩余能量的区间划分等三维状态示例# 假设每个区间还有额外的状态属性 dp [[[0]*K for _ in range(n)] for __ in range(n)] for length in range(2, n1): for i in range(n-length1): j i length - 1 for k in range(K): # 多维状态转移 for m in range(K): dp[i][j][k] min(...)在实际编码竞赛中这类问题通常会给出明确的状态维度提示关键是要准确识别哪些额外信息需要纳入状态定义。 
长河君 · 2026/10/29 22:43:29 · 阅读 1.2k 区间动态规划(DP)核心原理与实战应用
1. 区间DP的本质与适用场景区间动态规划Interval DP是动态规划算法中一个极具特色的分支它专门处理那些需要将问题分解为连续子区间进行求解的场景。与常规线性DP不同区间DP的核心在于区间划分的思想——通过枚举所有可能的区间分割点将大问题拆解为相互关联的子问题。1.1 什么情况下应该选择区间DP当问题满足以下三个特征时区间DP往往是最佳选择问题可分解为连续子区间如字符串的子串、数组的连续子序列、时间段的连续区间等子问题具有重叠性不同区间的计算会重复使用相同子问题的解满足最优子结构大区间的最优解能由其包含的小区间最优解组合得到典型应用场景包括矩阵链乘法的最优计算顺序回文子序列/子串相关问题石子合并类的最优代价问题括号匹配的最大长度计算多边形三角剖分的最小得分提示区间DP的时间复杂度通常为O(n³)因为需要枚举区间起点、终点和分割点。当n500时可能需要优化或考虑其他算法。1.2 区间DP与线性DP的本质区别以经典的背包问题线性DP和石子合并问题区间DP对比特征线性DP区间DP状态定义dp[i]表示前i个元素dp[i][j]表示区间i到j转移方向单向递推前→后区间长度递增短→长子问题关系相邻状态依赖任意子区间组合依赖典型问题背包、LIS矩阵链乘、回文分割这种二维状态的设计使得区间DP能精确捕捉子区间之间的复杂关系但也带来了更高的空间复杂度。2. 区间DP的标准解题框架2.1 状态设计的黄金法则区间DP的状态定义通常遵循固定模式dp[i][j] 表示区间[i,j]的最优解或某种性质例如石子合并dp[i][j]表示合并第i到第j堆石子的最小代价最长回文子序列dp[i][j]表示子串s[i..j]的最长回文子序列长度关键点在于区间端点i,j必须明确包含解的范围状态值要能通过更小区间的状态组合得到通常需要配合前缀和等辅助数组进行计算2.2 三重循环的模板结构区间DP的标准实现包含三个嵌套循环# 初始化 n len(data) dp [[0]*n for _ in range(n)] # 枚举区间长度 for length in range(2, n1): # 枚举区间起点 for i in range(n - length 1): j i length - 1 # 计算终点 dp[i][j] INF # 初始化为极大值 # 枚举分割点 for k in range(i, j): # 状态转移方程 dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost(i,j,k))这个模板的精妙之处在于外层按区间长度递增计算确保子问题先于父问题求解中层控制区间滑动窗口的位置内层尝试所有可能的分割方案2.3 边界条件处理技巧边界处理是区间DP最容易出错的部分常见处理方式单元素区间通常dp[i][i]有明确初值for i in range(n): dp[i][i] 0 # 或根据问题设定其他初值相邻元素区间有些问题需要单独初始化for i in range(n-1): dp[i][i1] data[i] data[i1] # 如石子合并无效区间ij时通常设为0或Noneif i j: dp[i][j] 03. 经典问题实战解析3.1 石子合并问题问题描述有N堆石子排成一列每次只能合并相邻的两堆代价为两堆石子数量之和。求将所有石子合并为一堆的最小总代价。状态转移方程推导dp[i][j] min(dp[i][k] dp[k1][j]) sum[i][j], for k in [i,j-1]其中sum[i][j]表示第i到第j堆石子的总数可以用前缀和数组快速计算。完整实现def stoneMerge(stones): n len(stones) prefix [0]*(n1) for i in range(n): prefix[i1] prefix[i] stones[i] dp [[0]*n for _ in range(n)] for length in range(2, n1): for i in range(n-length1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): cost prefix[j1] - prefix[i] dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost) return dp[0][n-1]复杂度分析时间复杂度O(n³) 三重循环空间复杂度O(n²) DP表存储3.2 最长回文子序列问题描述给定字符串s求其最长回文子序列的长度子序列不要求连续。关键观察如果s[i]s[j]则dp[i][j] dp[i1][j-1] 2否则dp[i][j] max(dp[i1][j], dp[i][j-1])实现代码def longestPalindromeSubseq(s): n len(s) dp [[0]*n for _ in range(n)] for i in range(n-1, -1, -1): # 逆序枚举起点 dp[i][i] 1 for j in range(i1, n): if s[i] s[j]: dp[i][j] dp[i1][j-1] 2 else: dp[i][j] max(dp[i1][j], dp[i][j-1]) return dp[0][n-1]注意事项这里采用逆序枚举i的技巧确保子问题先求解当ij时单个字符本身就是长度为1的回文空间复杂度可优化到O(n)使用滚动数组4. 区间DP的优化技巧4.1 四边形不等式优化对于某些满足单调性的区间DP问题可以将O(n³)优化到O(n²)。核心思想是利用决策单调性减少内层循环次数。适用条件代价函数满足四边形不等式状态转移方程形如dp[i][j] min(dp[i][k] dp[k1][j]) w(i,j)优化后的模板# 记录最优分割点 pos [[0]*n for _ in range(n)] for length in range(2, n1): for i in range(n-length1): j i length - 1 # 缩小k的枚举范围 start pos[i][j-1] if length 2 else i end pos[i1][j] if length 2 else j-1 dp[i][j] float(inf) for k in range(start, end1): if dp[i][k] dp[k1][j] w(i,j) dp[i][j]: dp[i][j] dp[i][k] dp[k1][j] w(i,j) pos[i][j] k4.2 记忆化搜索实现对于边界条件复杂的问题可以采用记忆化搜索递归缓存的方式实现更符合直觉。from functools import lru_cache def intervalDP(s): n len(s) lru_cache(maxsizeNone) def dfs(i, j): if i j: return 0 if i j: return 1 if s[i] s[j]: return dfs(i1, j-1) 2 return max(dfs(i1, j), dfs(i, j-1)) return dfs(0, n-1)优缺点比较优点代码直观边界处理简单缺点递归深度受限可能栈溢出常数时间较大5. 高频面试题精讲5.1 戳气球问题LeetCode 312题有n个气球每个气球标有数字。戳破气球i可以获得nums[i-1]*nums[i]*nums[i1]的硬币。求能获得的最大硬币数。关键思路逆向思考考虑最后戳破的气球kdp[i][j]表示戳破(i,j)区间内所有气球能获得的最大硬币数状态方程dp[i][j] max(dp[i][k] dp[k][j] nums[i]*nums[k]*nums[j]) for k in (i,j)实现代码def maxCoins(nums): nums [1] nums [1] n len(nums) dp [[0]*n for _ in range(n)] for length in range(2, n): for i in range(n-length): j i length for k in range(i1, j): dp[i][j] max(dp[i][j], dp[i][k] dp[k][j] nums[i]*nums[k]*nums[j]) return dp[0][n-1]5.2 多边形三角剖分LeetCode 1039题将凸多边形剖分成若干个三角形每个三角形的得分为三个顶点值的乘积求最小总得分。解法分析将多边形顶点按顺序编号为0到n-1dp[i][j]表示顶点i到j构成的多边形的最小得分枚举中间顶点k形成三角形(i,k,j)状态转移dp[i][j] min(dp[i][k] dp[k][j] values[i]*values[j]*values[k]) for k in range(i1, j)实现要点需要处理环形结构通常固定一条边作为基准初始化所有相邻两点dp[i][i1]06. 区间DP的常见陷阱与调试技巧6.1 易错点排查清单区间端点定义不清确认dp[i][j]是包含还是排除端点检查循环边界是否漏算或多算初始化不完整忘记初始化length1或length2的情况边界条件如ij未处理分割点枚举不全k的范围是否覆盖所有可能分割是否漏掉某些特殊分割情况状态转移条件错误合并代价计算是否正确是否考虑了所有可能的转移路径6.2 调试方法论小规模测试用n3,4的简单案例手动验证打印每个length的完整dp表可视化工具def print_dp(dp): for row in dp: print( .join(f{x:3d} if x!float(inf) else inf for x in row)) print()对比暴力法对小规模数据编写暴力递归解法交叉验证DP结果的正确性断点检查在关键转移步骤添加断言assert dp[i][k] dp[k1][j] cost 0, fInvalid at {i},{j},{k}7. 从模板到变式思维拓展训练7.1 环形区间问题处理对于环形排列的问题如环形石子合并常用解决方法是将原始数组复制一份接在后面长度2n对扩展后的数组进行常规区间DP最终结果为所有dp[i][in-1]中的最优解示例代码def circularStoneMerge(stones): n len(stones) extended stones stones prefix [0]*(2*n1) for i in range(2*n): prefix[i1] prefix[i] extended[i] dp [[0]*(2*n) for _ in range(2*n)] for length in range(2, n1): for i in range(2*n-length1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): cost prefix[j1] - prefix[i] dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] cost) return min(dp[i][in-1] for i in range(n))7.2 高维区间DP拓展某些问题可能需要更高维的状态表示如加入状态参数dp[i][j][k]表示区间i到j在某种状态k下的最优解例子带颜色标记的石子合并、考虑剩余能量的区间划分等三维状态示例# 假设每个区间还有额外的状态属性 dp [[[0]*K for _ in range(n)] for __ in range(n)] for length in range(2, n1): for i in range(n-length1): j i length - 1 for k in range(K): # 多维状态转移 for m in range(K): dp[i][j][k] min(...)在实际编码竞赛中这类问题通常会给出明确的状态维度提示关键是要准确识别哪些额外信息需要纳入状态定义。