信息技术大学
一维动态规划
数据结构与算法·面试高频 · 第 4 章 算法思想
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
一维动态规划
数据结构与算法·面试高频 · 第 4 章 算法思想
爬楼梯与打家劫舍
DP 入门双雄：今天的选择只依赖前一两天、前一家，状态转移一句话说完。
爬楼梯
f(n)=f(n−1)+f(n−2)，滚动两个变量即可
打家劫舍
偷或不偷，取前家与前两家的最大值
滚动压缩
只依赖最近几个状态，数组压成常数
最大子数组和
前缀带负就丢：dp[i] = max(nums[i], dp[i−1]+nums[i])，全局另记峰值。
状态定义
dp[i] = 以 i 结尾的最大子数组和
转移
另起炉灶或接上前一个，二者取大
变体
环彂数组、乘积最大（正负成对记录）
分割类问题
单词拆分、最少回文分割：枚举最后一刀，前半结果直接查表。
单词拆分
dp[i] = 存在 j 使 dp[j] 且 s[j..i] 在词典
回文分割
回文表预处理，枚举最后一段取最优
套路
「能否 / 最少几段」都靠枚举切点
状态机 DP
手里有货没货、今天冷冻不冷冻：每天是状态图上的一次转移，画图再写。
状态定义
持股、空仓、冷冻各设状态互转
转移图
画状态转移图，边上标代价与收益
优势
手续费、冷冻期等约束不再靠贪心硬猜
本节要点
- ✓爬楼梯与劫舍：只依赖近几步
- ✓子数组和：另起炉灶或接着走
- ✓分割类：枚举最后一刀查表
- ✓状态机：画转移图写 DP
延伸主题：刷打家劫舍 II 环形版写一遍单词拆分
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1最大子数组和为什么「负前缀直接丢」是对的？
参考答案dp[i−1] 为负时接上只会拖累 nums[i]，另起炉灶必然不差——这正是转移取 max 的含义。贪心视角等价：滚动和为负就清零重开。
2DP 与记忆化递归什么关系？各适合什么场景？
参考答案同一枚举的两面：记忆化自顶向下，只算需要的状态，状态稀疏时省；递推自底向上，无栈开销、可滚动压缩，状态稠密时优。先想清转移，再选实现。
3股票带冷冻期为什么必须状态机？
参考答案「今天能否买」取决于「昨天是否卖」，约束跨天且有互斥状态。把持股、空仓、冷冻各设状态互相转移，约束变成图上的边，清晰且不易漏。