预计阅读时间：3 分钟

优化DP

朴素转移超时，不是 DP 的终点，而是优化的起点。本合集收录「先写对、再打磨复杂度」的 DP 优化技巧题（状态怎么设计的题在《DP 状态设计》里）。

前缀和优化

leetcode 3699

题意：统计长度为 n、每个元素都在 $[l, r]$ 内的数组个数，要求相邻元素不相等，且任意连续三个元素都不构成严格递增或严格递减（即上升、下降交替出现），答案对 $10^9+7$ 取模。$3 \le n \le 2000$，$1 \le l < r \le 2000$。

寻找子问题：如果长度为 i 的序列此刻是「递增收尾」的（第 i 个数大于第 i-1 个数，下标从 1 开始），那它的前一个状态必须是「递减收尾」的，否则最后三个数严格递增。于是状态需要两个维度、两个数组：维度 i 表示当前序列长度，维度 j 表示当前结尾的数字；dp1 表示以递增收尾的方案数，dp2 表示以递减收尾的方案数，两者的转移完全对称。为简化计算，把值域 $[l, r]$ 平移到 $[0, r-l]$。

dp1[i][j] = dp2[i - 1][0] + dp2[i - 1][1] + ... + dp2[i - 1][j - 1]
dp2[i][j] = dp1[i - 1][j + 1] + dp1[i - 1][j + 2] + ... + dp1[i - 1][r - l]

初值：长度为 1 时还谈不上升降，两种收尾都算上，dp1[1][j] = dp2[1][j] = 1。答案 = sum(dp1[n]) + sum(dp2[n])：长度至少为 2 的数组最后一步非升即降，两类不重叠。全程对 $10^9+7$ 取模。

记值域宽度 $m = r - l + 1$。直接计算是 $O(n m^2)$：要枚举长度 i、结尾 j，还要枚举上一位可选的数字 k。观察到转移是连续区间的累加和，用前缀和把每次转移压到 $O(1)$，整体降为 $O(n m)$。

两个工程细节：

• 每一层递推只依赖前一层，用滚动数组压掉一维，空间从 $O(n m)$ 降到 $O(m)$；
• 前缀和用 itertools.accumulate 计算，比手写逐项循环快，Python 写法更稳。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。