用pdf怎么做电子书下载网站,如何做融资网站,网站推广关键词,重庆九龙坡营销型网站建设公司推荐线性 DP 的一种#xff0c;简称为「区间 DP」。以「区间长度」划分阶段#xff0c;以两个坐标#xff08;区间的左、右端点#xff09;作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。
一、概念
间 DP 的主要思想就是#xff1a;先在小区间内得到…线性 DP 的一种简称为「区间 DP」。以「区间长度」划分阶段以两个坐标区间的左、右端点作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。
一、概念
间 DP 的主要思想就是先在小区间内得到最优解再利用小区间的最优解合并从而得到大区间的最优解最终得到整个区间的最优解。
根据小区间向大区间转移情况的不同常见的区间 DP 问题可以分为两种
单个区间从中间向两侧更大区间转移的区间 DP 问题。比如从区间 [i1,j−1]转移到更大区间 [i,j]。多个大于等于 2 个小区间转移到大区间的区间 DP 问题。比如从区间 [i,k]和区间 [k,j]转移到区间 [i,j]。
二、区间 DP 问题的基本思路
1. 第 1 种区间 DP 问题基本思路
从中间向两侧转移的区间 DP 问题的状态转移方程一般为dp[i][j]max{dp[i1][j−1],dp[i1][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;// 创建二维数组 dpdp[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 状态转移 枚举中间断点 kdp[i][j] min(dp[i][j], dp[i][k] dp[k][j] p[i] * p[k] * p[j]) 初始化 dp[i][i1] 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][i1] 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)); // 输出最小乘法次数示例说明
输入[10, 30, 5, 60] 代表三个矩阵 A1: 10x30 A2: 30x5 A3: 5x60
可以有两种乘法顺序 ((A1 * A2) * A3)代价 10*30*5 10*5*60 1500 3000 4500 (A1 * (A2 * A3))代价 30*5*60 10*30*60 9000 18000 27000
取较小值 最小代价为 4500 请观看配套视频《数据结构与算法前端版》
