动态规划进阶：转移方程优化技巧全解

动态规划（DP）的核心是“定义状态+推导转移方程”，但很多时候，基础的转移方程会导致时间复杂度偏高（如$O(n^2)$），难以应对大规模输入，此时转移方程的优化就成为突破性能瓶颈的关键。

一、优化的核心目标与前提

在深入技巧之前，我们需要明确：转移方程优化的本质是减少冗余计算。当基础转移方程中存在“重复查询区间最值”“线性函数最值”“累加区间和”等操作时，就有优化的空间。

1.1 常见可优化的转移方程形式

• 区间最值型：$dp[i]={\max }_{j\in [i-k,i-1]}(dp[j]+w(i,j))$（如滑动窗口类DP）；

• 线性函数型：$dp[i]={\min }_{j<i}(a[i]\cdot b[j]+c[j]+d[i])$（如任务安排问题）；

• 区间累加型：$dp[i]={\sum }_{j=l[i]}^{r[i]}dp[j]+w[i]$（如区间和依赖的DP）；

• 线性递推型：$dp[i]=k_1\cdot dp[i-1]+k_2\cdot dp[i-2]+\cdots +k_m\cdot dp[i-m]$（如斐波那契数列的高阶扩展）。

1.2 优化的前提

• 能从转移方程中提取出“可复用的结构”（如单调关系、线性函数、区间和等）；
• 优化后能减少状态转移的计算量（如从$O(n)$ per step降至$O(1)$或$O(\log n)$）。

二、单调队列优化：区间最值的高效查询

单调队列优化适用于**转移方程中需要查询“滑动窗口内最值”**的场景，其核心是用一个“单调队列”维护候选状态$j$，使每次查询最值的时间从$O(n)$降至$O(1)$。

2.1 适用场景

转移方程形如：

$dp[i]={\max }_{j\in [L(i),R(i)]}(dp[j]+w(i,j))$

其中$L(i)$和$R(i)$是关于$i$的单调函数（如$L(i)=i-k$，$R(i)=i-1$），即窗口范围随$i$单调变化。

2.2 核心思想

1. 维护单调队列：队列中存储候选$j$的索引，且对应的$dp[j]+w(i,j)$保持单调（递增或递减）；
2. 窗口裁剪：当$j$超出窗口范围$[L(i),R(i)]$时，从队首移除；
3. 高效更新：新$j$加入队列时，从队尾移除所有“比当前$j$差”的候选（即$dp[j]+w(i,j)$不优的），确保队列单调性。

2.3 案例：滑动窗口最大值的DP版本

问题：给定数组$nums$和窗口大小$k$，求每个位置$i$对应的窗口$[i-k+1,i]$内的最大值（用DP思想实现）。

基础转移方程：

$dp[i]={\max }_{j=i-k+1}^{i}nums[j]$（$dp[i]$表示以$i$为结尾的窗口最大值）

优化思路：用单调队列存储窗口内元素的索引，队列保持元素值递减，队首即为当前窗口最大值。

public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] dp = new int[n - k + 1]; // 结果数组Deque<Integer> deque = new ArrayDeque<>(); // 单调队列（存储索引）for (int i = 0; i < n; i++) {// 1. 移除窗口外的元素（索引 <= i - k）while (!deque.isEmpty() && deque.peekFirst() <= i - k) {deque.pollFirst();}// 2. 移除队尾比当前元素小的元素（它们不可能是最大值）while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {deque.pollLast();}// 3. 加入当前元素索引deque.offerLast(i);// 4. 窗口形成后，记录最大值（队首元素）if (i >= k - 1) {dp[i - k + 1] = nums[deque.peekFirst()];}}return dp;
}

复杂度分析：每个元素入队和出队各一次，总时间$O(n)$，空间$O(k)$（队列最大存储$k$个元素）。

三、斜率优化：线性函数的最值求解

斜率优化适用于转移方程可转化为线性函数最值问题的场景，通过将状态$j$映射为直线，将“求$dp[i]$”转化为“求直线在某点的最值”，再用凸包或单调队列维护直线集合。

3.1 适用场景

转移方程形如：

$dp[i]={\min }_{j<i}(a[i]\cdot b[j]+c[j]+d[i])$

其中$a[i]$和$d[i]$是仅与$i$相关的函数，$b[j]$和$c[j]$是仅与$j$相关的函数。可改写为：

$dp[i]=d[i]+{\min }_{j<i}(b[j]\cdot a[i]+c[j])$

此时，每个$j$对应一条直线$y=b[j]\cdot x+c[j]$，$dp[i]$即为$x=a[i]$时所有直线的最小值（加$d[i]$）。

3.2 核心思想

1. 直线映射：将每个$j$映射为直线$y=k_j\cdot x+b_j$（$k_j=b[j]$，$b_j=c[j]$）；
2. 维护有效直线集：若直线$l_1$在所有$x$上均不如$l_2$优，则$l_1$可被淘汰（凸包优化）；
3. 查询最值：对于$x=a[i]$，在有效直线集中找到最优直线（如斜率单调时用单调队列，否则用二分查找）。

3.3 案例：任务安排问题

问题：$n$个任务按顺序执行，每次启动机器需支付固定成本$S$，第$i$个任务的成本为$t[i]$，且成本随启动后时间累积（启动后第$k$个任务的成本为$t[i]\cdot k$）。求总最小成本。

基础转移方程：

$dp[i]={\min }_{j<i}(dp[j]+S+{\sum }_{k=j+1}^{i}t[k]\cdot (k-j))$

通过前缀和优化$\sum$项后，可转化为：

$dp[i]={\min }_{j<i}(dp[j]-sumT[j]\cdot j)+sumT[i]\cdot i+S-sumT[j]$

其中$sumT[i]$是$t$的前缀和。

令$a[i]=sumT[i]$，$b[j]=j$，$c[j]=dp[j]-sumT[j]\cdot j-sumT[j]$，则：

$dp[i]=a[i]\cdot i+S+{\min }_{j<i}(-b[j]\cdot a[i]+c[j])$

符合线性函数形式，可通过斜率优化求解。

public long minCost(int[] t, int S) {int n = t.length;long[] sumT = new long[n + 1]; // 前缀和：sumT[i] = t[0]+...+t[i-1]for (int i = 1; i <= n; i++) {sumT[i] = sumT[i - 1] + t[i - 1];}long[] dp = new long[n + 1];Deque<Line> deque = new ArrayDeque<>();// 初始直线：j=0时，k=-b[0]=0，b=c[0]=dp[0] - sumT[0]*0 - sumT[0] = 0 - 0 - 0 = 0deque.offerLast(new Line(0, 0));for (int i = 1; i <= n; i++) {long x = sumT[i]; // 当前x = a[i] = sumT[i]// 1. 弹出队首无效直线（斜率递增时，前面的直线在x处已不是最优）while (deque.size() >= 2) {Line l1 = deque.pollFirst();Line l2 = deque.peekFirst();if (getY(l1, x) >= getY(l2, x)) {// l1不如l2优，移除} else {deque.addFirst(l1); // 恢复l1，退出break;}}// 2. 计算当前dp[i]Line best = deque.peekFirst();dp[i] = x * i + S + getY(best, x);// 3. 加入当前j=i对应的直线long k = -i; // k_j = -b[j] = -jlong b = dp[i] - sumT[i] * i - sumT[i]; // c[j] = dp[j] - sumT[j]*j - sumT[j]Line newLine = new Line(k, b);// 4. 弹出队尾无效直线（确保队列斜率递增，且新直线更优）while (deque.size() >= 2) {Line l2 = deque.pollLast();Line l1 = deque.peekLast();// 若l1与l2的交点 >= l2与newLine的交点，则l2无效if (intersectionX(l1, l2) >= intersectionX(l2, newLine)) {// 移除l2} else {deque.addLast(l2); // 恢复l2，退出break;}}deque.addLast(newLine);}return dp[n];
}// 直线类：y = k*x + b
static class Line {long k, b;Line(long k, long b) {this.k = k;this.b = b;}
}// 计算直线在x处的y值
static long getY(Line l, long x) {return l.k * x + l.b;
}// 计算两条直线的交点x坐标（分数形式避免精度问题，此处简化为double）
static double intersectionX(Line l1, Line l2) {return (double) (l2.b - l1.b) / (l1.k - l2.k);
}

复杂度分析：每个$i$对应的直线入队和出队各一次，总时间$O(n)$，空间$O(n)$。

四、前缀和优化：区间累加的快速计算

前缀和优化适用于转移方程中需要累加区间和的场景，通过预处理前缀和数组，将$O(n)$的区间累加转为$O(1)$查询。

4.1 适用场景

转移方程形如：

$dp[i]={\sum }_{j=l[i]}^{r[i]}dp[j]+w[i]$

其中$l[i]$和$r[i]$是$i$的函数，区间和的计算是瓶颈。

4.2 核心思想

1. 预处理前缀和：定义$pre[i]={\sum }_{j=0}^{i}dp[j]$，则区间和${\sum }_{j=l}^{r}dp[j]=pre[r]-pre[l-1]$；

2. 替换转移方程：用前缀和表达式替代原区间和，将每次转移的计算量从$O(n)$降至$O(1)$。

4.3 案例：最大子段和（带长度限制）

问题：给定数组$nums$和最大长度$k$，求长度不超过$k$的连续子数组的最大和。

基础转移方程：

$dp[i]={\max }_{j=\max (0,i-k)}^{i-1}(dp[j]+nums[i])$（$dp[i]$表示以$i$结尾的最大和）

优化思路：用前缀和$pre[i]$记录$dp[\mathrm{0..}i]$的和，但更优的是结合单调队列维护区间最大值（同时用前缀和优化累加）。

public int maxSubarraySumWithLimit(int[] nums, int k) {int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];int maxSum = dp[0];// 前缀和数组int[] pre = new int[n];pre[0] = dp[0];for (int i = 1; i < n; i++) {pre[i] = pre[i - 1] + dp[i];}Deque<Integer> deque = new ArrayDeque<>();deque.offer(0);for (int i = 1; i < n; i++) {// 移除窗口外的j（j < i - k）while (!deque.isEmpty() && deque.peekFirst() < i - k) {deque.pollFirst();}// dp[i] = max(dp[j] for j in [i-k, i-1]) + nums[i]// 用单调队列的队首获取max(dp[j])dp[i] = nums[i] + (deque.isEmpty() ? 0 : dp[deque.peekFirst()]);// 维护单调队列（递减）while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {deque.pollLast();}deque.offer(i);maxSum = Math.max(maxSum, dp[i]);}return maxSum;
}

复杂度分析：前缀和优化后，区间和查询为$O(1)$，结合单调队列维护最值，总时间$O(n)$。

五、状态压缩与滚动数组：空间维度的优化

状态压缩适用于转移方程中当前状态仅依赖有限个前驱状态的场景，通过减少DP数组的维度（如二维→一维），降低空间复杂度。

5.1 适用场景

• 二维DP中，$dp[i][j]$仅依赖$dp[i-1][j]$和$dp[i][j-1]$（如0/1背包、最长公共子序列）；
• 高维DP中，状态仅依赖前$k$层（如$dp[i][j][k]$仅依赖$dp[i-1][j][k]$）。

5.2 核心思想

1. 识别依赖关系：确定当前状态依赖的前驱状态范围（如仅前一行或前一列）；
2. 复用空间：用一维数组替代二维数组，通过“滚动”更新覆盖旧状态（注意遍历顺序，避免覆盖未使用的前驱状态）。

5.3 案例：0/1背包的空间优化

基础二维转移方程：

$dp[i][j]=\max (dp[i-1][j],dp[i-1][j-w[i]]+v[i])$（前$i$个物品，容量$j$的最大价值）

优化后一维转移方程：

$dp[j]=\max (dp[j],dp[j-w[i]]+v[i])$（逆序遍历容量$j$，避免重复使用同一物品）

public int knapsack(int[] w, int[] v, int C) {int n = w.length;int[] dp = new int[C + 1];for (int i = 0; i < n; i++) {// 逆序遍历容量，防止同一物品被多次选择for (int j = C; j >= w[i]; j--) {dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);}}return dp[C];
}

复杂度分析：空间复杂度从$O(n\cdot C)$降至$O(C)$，时间复杂度仍为$O(n\cdot C)$。

六、矩阵快速幂：线性递推的加速

矩阵快速幂适用于线性递推关系的DP问题（如斐波那契数列、线性 recurrence），当$n$很大时（如$n\le 10^9$），可将时间复杂度从$O(n)$降至$O(\log n)$。

6.1 适用场景

转移方程形如线性递推：

$dp[i]=a_1\cdot dp[i-1]+a_2\cdot dp[i-2]+\cdots +a_k\cdot dp[i-k]$

可表示为矩阵乘法：$\left[\begin{array}{c}dp[i]\\ dp[i-1]\\ ⋮\\ dp[i-k+1]\end{array}\right]=M\cdot \left[\begin{array}{c}dp[i-1]\\ dp[i-2]\\ ⋮\\ dp[i-k]\end{array}\right]$，其中$M$是转移矩阵。

6.2 核心思想

1. 构建转移矩阵：将递推关系转化为矩阵乘法形式；
2. 矩阵幂加速：用快速幂计算转移矩阵的$n$次幂，再与初始向量相乘，得到$dp[n]$。

6.3 案例：斐波那契数列第n项

递推关系：$dp[i]=dp[i-1]+dp[i-2]$（$dp[0]=0$，$dp[1]=1$）

矩阵形式：$\left[\begin{array}{c}dp[i]\\ dp[i-1]\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}dp[i-1]\\ dp[i-2]\end{array}\right]$

public int fib(int n) {if (n <= 1) return n;// 转移矩阵：[[1,1],[1,0]]int[][] mat = {{1, 1}, {1, 0}};// 计算mat^(n-1)int[][] matPow = matrixPower(mat, n - 1);// 初始向量[dp[1], dp[0]] = [1, 0]return matPow[0][0] * 1 + matPow[0][1] * 0;
}// 矩阵快速幂：计算mat^power
int[][] matrixPower(int[][] mat, int power) {int n = mat.length;// 初始化单位矩阵int[][] result = new int[n][n];for (int i = 0; i < n; i++) {result[i][i] = 1;}while (power > 0) {if (power % 2 == 1) {result = matrixMultiply(result, mat);}mat = matrixMultiply(mat, mat);power /= 2;}return result;
}// 矩阵乘法：a * b
int[][] matrixMultiply(int[][] a, int[][] b) {int n = a.length;int[][] res = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {res[i][j] += a[i][k] * b[k][j];}}}return res;
}

复杂度分析：矩阵乘法时间为$O(k^3)$（$k$为矩阵维度），快速幂迭代$O(\log n)$次，总时间$O(k^3\log n)$，适用于$n$极大的场景。

七、优化技巧的选择与总结

优化技巧	适用场景	时间复杂度优化	核心工具/思想
单调队列优化	区间最值查询（窗口单调）	$O(n^2)\to O(n)$	单调队列维护候选集
斜率优化	线性函数最值（$dp[i]=a[i]\cdot b[j]+\dots$）	$O(n^2)\to O(n)$	凸包/单调队列维护直线集
前缀和优化	区间累加求和	$O(n^2)\to O(n)$	前缀和数组快速查询
状态压缩	状态依赖有限前驱	空间$O(n^2)\to O(n)$	滚动数组复用空间
矩阵快速幂	线性递推（$n$极大）	$O(n)\to O(\log n)$	矩阵乘法与快速幂

选择策略

1. 若转移方程涉及“区间最值”且窗口单调：优先用单调队列优化；
2. 若转移方程可化为线性函数形式：用斜率优化；
3. 若涉及“区间和累加”：用前缀和优化；
4. 若空间复杂度过高且状态依赖简单：用状态压缩；
5. 若$n$极大且是线性递推：用矩阵快速幂。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～