DP优化概述

What · 是什么

DP 优化的总目标是降低转移时间复杂度。朴素 DP 常因枚举全部决策 j 而达到 O(n²) 甚至更高。优化手段按性质分类：①数据结构加速（前缀和、线段树、树状数组、单调队列/栈、平衡树、堆）；②数学性质（决策单调性/四边形不等式/斜率优化/WQS二分、矩阵快速幂加速线性递推）；③状态设计（状态压缩、滚动数组降空间、卷积/FFT 加速组合转移、倍增优化）。多数优化把「对每个状态枚举所有决策」变为「用数据结构或单调性快速求最优决策」。

Why · 为什么

How · 实现

伪代码

# 优化选型速查
# w(j,i) 可拆成 (A_i 项) + (B_j 项) + (C_i*D_j 交叉项) -> 斜率优化
# w(j,i) 是滑动窗口区间最值         -> 单调队列
# opt(i) 单调 + w 满足四边形不等式   -> 分治优化 / Knuth / 二分队列
# 转移是简单加和（区间和）          -> 前缀和优化
# 递推可写成矩阵（线性）            -> 矩阵快速幂
# 只关心上一步状态                 -> 滚动数组

判断决策单调性步骤:
1. 写出 f(i)=min_j {f(j)+w(j,i)}
2. 验证 w 是否满足四边形不等式 (a<=b<=c<=d => w(a,c)+w(b,d)<=w(a,d)+w(b,c))
3. 满足 -> 使用决策单调性优化

Python 实现

def prefix_sum_opt(a):
    """前缀和优化 DP 演示：f[i] = 前 i 项中最小子段和，O(n)。
    对应 w(j,i)=sum(a[j+1..i]) 可拆成前缀和差，避免每段重算。"""
    n = len(a)
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] + a[i]
    # 经典 O(n)：维护前缀最小前缀和
    min_pref = 0
    best = float('-inf')
    for i in range(1, n + 1):
        best = max(best, pref[i] - min_pref)
        min_pref = min(min_pref, pref[i])
    return best


def monotonic_queue_dp(a, k):
    """单调队列优化：f[i] = max(a[i-k..i]) 滑动窗口最值，O(n)。
    是 DP 优化里最基础的「维护候选集」模板。"""
    from collections import deque
    dq = deque()
    res = []
    for i, x in enumerate(a):
        while dq and dq[0] < i - k:
            dq.popleft()
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        res.append(a[dq[0]])
    return res


def rolling_array(dp0, dp1):
    """滚动数组演示：只保留上一行，空间 O(n)。
    通常用于背包等 f[i][j] 只依赖 f[i-1][*] 的转移。"""
    return dp1, dp0


def matrix_pow_transfer(trans, steps):
    """矩阵快速幂优化线性递推：f_{n+1} = M * f_n。
    O(log n) 次矩阵乘代替 O(n) 次迭代。"""
    def mul(A, B):
        k = len(A)
        C = [[0] * k for _ in range(k)]
        for i in range(k):
            Ai = A[i]
            Ci = C[i]
            for t in range(k):
                if Ai[t]:
                    Bt = B[t]
                    for j in range(k):
                        Ci[j] += Ai[t] * Bt[j]
        return C
    k = len(trans)
    res = [[1 if i == j else 0 for j in range(k)] for i in range(k)]
    while steps:
        if steps & 1:
            res = mul(res, trans)
        trans = mul(trans, trans)
        steps >>= 1
    return res


if __name__ == "__main__":
    # 前缀和优化：最大子段和
    a = [3, -1, 2, -5, 4, 6, -2]
    assert prefix_sum_opt(a) == 10  # 4+6
    assert prefix_sum_opt([-3, -1, -2]) == -1
    # 单调队列滑动窗口
    a = [1, 3, -1, -3, 5, 3, 6, 7]
    assert monotonic_queue_dp(a, 3) == [1, 3, 3, 3, 5, 5, 6, 7]
    # 矩阵快速幂：Fibonacci（M=[[1,1],[1,0]]）
    M = [[1, 1], [1, 0]]
    f = matrix_pow_transfer(M, 10)  # F_10 = 55
    assert f[0][0] == 89 and f[0][1] == 55
    print("All tests passed.")

易错点

• 先写朴素 DP 确认转移结构，再套优化——跳过朴素直接套优化易把式子写错
• 混淆「优化转移时间」与「优化状态空间」（滚动数组不能降低时间复杂度）
• 忘记验证单调性/凸性前提就套用斜率优化或四边形不等式
• 数据结构优化时未把「查询/插入」顺序对齐转移依赖（先查后插）

例题

信源

• OI Wiki✓ https://oi-wiki.org/dp/opt/dp-opt/
• CP-Algorithms✓ https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html