跳到主要内容

动态规划基础与线性状态

本节目标

从线性顺序中的前缀最优解出发，建立可滚动压缩的动态规划状态。

识别信号​

题目按下标、台阶或日期从左向右推进；当前位置的最优答案只依赖前面少数状态，且相邻选择、连续区间或符号变化会破坏贪心选择时，应优先考虑线性 DP。

状态定义与转移推导​

先让状态回答一个完整问题：到当前位置为止的最优值，或必须以当前位置结尾的最优值。爬楼梯累加最后一步的两种来源；打家劫舍区分取与不取；最大子数组和保留“以当前位置结尾”的和；乘积问题还必须同时保留最大与最小乘积。

初始化与遍历顺序​

状态总从小下标推到大下标。初始化覆盖最短合法前缀：计数题给一、最优值题给首元素或空前缀零。乘积转移遇负数前先交换最大和最小状态，遇零时自然从当前元素重新开始。

通用模板​

设 dp[i] 为处理到 i 的答案
从左到右枚举 i：
  根据能到达 i 的更小下标更新 dp[i]
  用 dp[i] 更新全局答案或下一轮滚动状态

空间优化与复杂度​

若 dp[i] 只读取固定个数的前驱，用两个或三个变量替代数组，空间降为 O(1)；遍历一次的时间为 O(n)。需要回溯具体方案时再保留完整数组和前驱。

母题序列​

  1. 爬楼梯（必学）：把最后一步拆成两个互斥来源。
  2. 最大子数组和（必学）：维护以当前位置结尾的连续区间。
  3. 打家劫舍（必学）：在相邻不可同取的约束下滚动决策。
  4. 乘积最大子数组（必学）：让负数在最大和最小状态间翻转角色。

常见误区​

  • 没说明状态是否必须以当前位置结尾，导致不连续元素被拼在一起。
  • 先覆盖滚动变量，再读取它计算另一个状态。
  • 乘积题只保存最大值，遗漏负数乘负数后的反转。
  • 用零初始化全局最优，错过全为负数的数组。

迁移方向​

当依赖仍在一条序列上但前驱不再只相邻，可迁移到序列 DP；当选择受容量约束，可迁移到背包；当状态来自二维坐标，则转向网格与路径 DP。