预计阅读时间：2 分钟

优化DP

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

前缀和优化

leetcode 3699

寻找子问题：如果长度为 n 的序列此刻是「递增收尾」的，那它的前一个状态必须是「递减收尾」的，且第 n 个数（index 从 1 开始）大于第 n-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]

直接计算是 $O(n^3)$：要枚举 i、j，还要枚举上一位可选的数字 k。观察到转移是连续区间的累加和，用前缀和把每次转移压到 $O(1)$，整体降为 $O(n^2)$。

两个工程细节：

• 此题数据大概率没用 Python 校过，直接写会超时；
• 每一层递推只依赖前一层，用滚动数组压掉一维，前缀和用 itertools.accumulate 加速计算，可以救回来。

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

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