区间dp

一、核心思想与适用题型

核心思想

区间DP的核心是将问题分解为子区间求解，通过解决子区间的最优解来构建整个区间的最优解。其基本思路是：

1. 定义状态表示区间[i, j]的属性
2. 通过枚举分割点将大区间划分为两个或多个子区间
3. 将子区间的解合并得到大区间的解

适用题型特征

• 问题涉及区间操作：如合并、分割、删除等
• 具有最优子结构：大区间的最优解可由子区间最优解推导
• 子问题重叠：不同区间可能包含相同子区间
• 典型问题：
  • 合并类：石子合并、能量项链
  • 回文类：最长回文子序列、回文分割
  • 括号类：合法括号序列、括号最大匹配
  • 分割类：多边形三角剖分、表达式加括号

二、通用解题框架

1. 状态定义

通常定义为二维数组，表示区间[i, j]的最优解：

 

# 最常见形式
dp[i][j] = 区间[i, j]的最优值# 有时需要额外维度表示状态
dp[i][j][k] = 区间[i, j]在状态k下的最优值

 

2. 状态转移方程

通用形式：

 

dp[i][j] = optimal{f(dp[i][k], dp[k+1][j])  # 枚举分割点kg(dp[i+1][j-1], ...)     # 根据端点情况
}

3. 初始化

 

# 基础情况：长度为1的区间
for i in range(n):dp[i][i] = base_value  # 如：石子合并中dp[i][i]=0# 有时需要初始化长度为2的区间
for i in range(n-1):dp[i][i+1] = calculate(i, i+1)

三、常见状态转移模型

1. 枚举分割点模型（最经典）

应用：石子合并、多边形三角剖分

通用转移方程：

 

dp[i][j] = min/max_{i≤k<j} {dp[i][k] + dp[k+1][j] + merge_cost(i, k, j)
}

2. 端点匹配模型

应用：最长回文子序列、括号匹配

通用转移方程：

 

if 端点匹配:dp[i][j] = dp[i+1][j-1] + 2
else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])

3. 区间分割模型

应用：回文分割、添加括号

通用转移方程：

 

dp[i][j] = min/max_{i≤k<j} {dp[i][k] + dp[k+1][j] + penalty(i, j)
}

六、解题模板总结

 

def interval_dp_template(arr):n = len(arr)# 1. 状态定义dp = [[0]*n for _ in range(n)]# 2. 初始化基础情况for i in range(n):dp[i][i] = base_case(arr[i])# 3. 区间长度递增遍历for length in range(2, n+1):for i in range(n-length+1):j = i + length - 1# 4. 根据问题类型选择转移方式# 类型A：枚举分割点if problem_type == "partition":dp[i][j] = init_valuefor k in range(i, j):dp[i][j] = combine(dp[i][j],dp[i][k] + dp[k+1][j] + merge_cost(i, k, j))# 类型B：端点匹配elif problem_type == "endpoint":if arr[i] == arr[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])# 5. 返回结果return dp[0][n-1]

七、易错点与注意事项

1. 遍历顺序：必须保证计算dp[i][j]时，其依赖的子区间dp[i][k]和dp[k+1][j]已经计算
2. 边界处理：注意区间长度、索引边界，特别是j = i+length-1不要越界
3. 初始化：根据问题合理初始化长度为1和2的区间
4. 环形处理：破环成链时，数组长度变为2n，最终结果在所有长度为n的区间中选取
5. 空间优化：某些情况下可以使用滚动数组优化空间，但会损失清晰性
6. 时间复杂度：O(n³)可能超时，考虑四边形不等式优化或贪心策略

 

 

 

例题：

题目链接：312. 戳气球 - 力扣（LeetCode）

 

 

 

 

 

 

 

 

 

class Solution {
public:int maxCoins(vector<int>& nums) {vector<vector<int>> dp(303, vector<int> (303));int n = nums.size();vector<int> value;value.push_back(1);for (int i = 0; i < n; i++) {value.push_back(nums[i]);}value.push_back(1);for (int i = n - 1; i >= 0; i--) {for (int j = i + 2; j <= n + 1; j++) {for (int k = i + 1; k < j; k++) {int sum = value[i] * value[k] * value[j];sum += dp[i][k] + dp[k][j];dp[i][j] = max(dp[i][j], sum);}}}return dp[0][n + 1];}
};