当前位置：首页 > news >正文

区间动态规划

news 2025/6/6 7:16:06

线性 DP 的一种，简称为「区间 DP」。以「区间长度」划分阶段，以两个坐标（区间的左、右端点）作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。

一、概念

间 DP 的主要思想就是：先在小区间内得到最优解，再利用小区间的最优解合并，从而得到大区间的最优解，最终得到整个区间的最优解。

根据小区间向大区间转移情况的不同，常见的区间 DP 问题可以分为两种：

单个区间从中间向两侧更大区间转移的区间 DP 问题。比如从区间 [i+1,j−1]转移到更大区间 [i,j]。
多个（大于等于 2 个）小区间转移到大区间的区间 DP 问题。比如从区间 [i,k]和区间 [k,j]转移到区间 [i,j]。

二、区间 DP 问题的基本思路

1. 第 1 种区间 DP 问题基本思路

从中间向两侧转移的区间 DP 问题的状态转移方程一般为：dp[i][j]=max{dp[i+1][j−1],dp[i+1][j],dp[i][j−1]}+cost[i][j], i <= j,。

其中 dp[i][j]表示为：区间 [i,j]（即下标位置 i到下标位置 j 上所有元素）上的最大价值。
cost 表示为：从小区间转移到区间 [i,j]的代价。
这里的 max/minn 取决于题目是求最大值还是求最小值。

从中间向两侧转移的区间 DP 问题的基本解题思路如下：

枚举区间的起点；
枚举区间的终点；
根据状态转移方程计算从小区间转移到更大区间后的最优值

// 假设 dp 是一个二维数组，表示区间DP的状态
// cost 表示区间内每个子问题的权值或代价// 逆序枚举区间起点
for (let i = size - 1; i >= 0; i--) {// 枚举区间终点for (let j = i + 1; j < size; j++) {// 状态转移方程，计算转移到更大区间后的最优值dp[i][j] = Math.max(dp[i + 1][j - 1], dp[i + 1][j], dp[i][j - 1]) + cost[i][j];}
}

2. 第 2 种区间 DP 问题基本思路

// 假设 dp 是一个二维数组，表示区间DP的状态
// cost 表示区间内每个子问题的权值或代价// 枚举区间长度
for (let l = 1; l < n; l++) {// 枚举区间起点for (let i = 0; i < n; i++) {// 根据起点和长度得到终点const j = i + l - 1;// 防止越界if (j >= n) {break;}// 初始化 dp[i][j]dp[i][j] = -Infinity;// 枚举区间分割点for (let k = i; k <= j; k++) {// 状态转移方程，计算合并区间后的最优值dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][j] + cost[i][j]);}}
}

三、练习

给定一个字符串 s找出其中最长的回文子序列，并返回该序列的长度。

代码

class Solution {longestPalindromeSubseq(s) {const size = s.length;// 创建二维数组 dp，dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长回文子序列的长度const dp = new Array(size).fill(0).map(() => new Array(size).fill(0));// 初始化区间长度为 1 的情况for (let i = 0; i < size; i++) {dp[i][i] = 1;}// 逆序枚举区间起点for (let i = size - 1; i >= 0; i--) {// 枚举区间终点for (let j = i + 1; j < size; j++) {// 如果区间两端字符相等，则当前区间的最长回文子序列长度为左下方的长度加上 2if (s[i] === s[j]) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {// 否则，取左侧和下侧的最大值dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}// 返回整个字符串的最长回文子序列长度return dp[0][size - 1];}
}// 示例用法
const solution = new Solution();
// 输出整个字符串的最长回文子序列长度
console.log(solution.longestPalindromeSubseq("bbbab"));

四、案例——问题：矩阵链乘法问题（Matrix Chain Multiplication）

描述：
给定一系列矩阵 A1, A2, ..., An，它们的维度为 p0 × p1, p1 × p2, ..., pn-1 × pn。
你的任务是决定这些矩阵的乘法顺序，使得乘法总操作次数最小。

注意：矩阵乘法满足结合律但不满足交换律。

🧠 思路：区间动态规划

状态定义：
- dp[i][j] 表示计算矩阵 Ai ~ Aj 的最小乘法次数（i < j）
状态转移：
- 枚举中间断点 k：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + p[i] * p[k] * p[j])
初始化：
- dp[i][i+1] = 0，因为两个相邻矩阵之间不能再分割
目标：
- dp[0][n]，表示从第一个矩阵乘到最后一个矩阵的最小代价

✅ JavaScript 实现

function matrixChainOrder(p) {const n = p.length - 1; // 有 n 个矩阵const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(Infinity));// 初始化对角线相邻的 dp[i][i+1] = 0for (let i = 0; i < n; i++) {dp[i][i + 1] = 0;}// 区间长度 l 从 2 到 nfor (let len = 2; len <= n; len++) {for (let i = 0; i + len <= n; i++) {const j = i + len;for (let k = i + 1; k < j; k++) {const cost = dp[i][k] + dp[k][j] + p[i] * p[k] * p[j];if (cost < dp[i][j]) {dp[i][j] = cost;}}}}return dp[0][n];
}// 示例：矩阵 A(10x30), B(30x5), C(5x60)
// 对应的维度数组 p = [10, 30, 5, 60]
const dimensions = [10, 30, 5, 60];
console.log(matrixChainOrder(dimensions)); // 输出最小乘法次数