線性 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)); // 輸出最小乘法次數
🧩 示例說明：
輸入：[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
請觀看配套視頻《數據結構與算法（前端版）》
