01先把问题说具体
房屋金额 [2,7,9,3,1],相邻房屋不能同时选择,最大可取多少?
02一步步得到方法
状态需要能描述完整子问题
定义 dp[i] 为前 i 间房屋中的最大合法收益,允许一间也不选。考虑第 i 间(数组下标 i−1):不选时答案为 dp[i−1];选它则前一间不能选,收益为 dp[i−2]+a[i−1]。
这两种情况互斥且覆盖所有合法方案,所以取最大。不是看到金额大就选,因为当前选择会限制后面相邻位置;局部最大金额不一定属于全局最优方案。
初值和滚动必须对应同一含义
dp[0]=0,第一间后 dp[1]=max(0,a[0])。滚动版本用 older 表示 dp[i−2],previous 表示 dp[i−1],先计算 current,再同时前移。
若题目强制至少选一间,含负数输入的初值要改;本课明确允许空选择。要恢复选了哪些房屋,通常保留完整 dp 表与选择记录。
先写中文定义,再确认下标范围
同样的 dp[i] 可以表示到达第 i 格的方案数,也可以表示前 i 件物品的最优值。两者基础状态和答案位置不同,写出一句精确定义比先套转移公式更重要。
滚动变量能省空间,是因为后续转移只依赖少数旧状态。覆盖前先确认哪些旧值还会被使用;若还要还原整条选择路径,仅保留一个最优值通常不够。
03把一个小例子完全算清楚
[2,7,9,3,1]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 前 1、2 间 | dp=2、7 | 第二间选 7 胜过 2 |
| 前 3 间 | max(7,2+9)=11 | 选 2 与 9 |
| 前 4 间 | max(11,7+3)=11 | 跳过金额 3 |
| 前 5 间 | max(11,11+1)=12 | 选下标 0、2、4 |
窄屏可左右滑动表格,阅读完整计算与理由。
答案 12,来自 2+9+1;状态代表整个前缀的最优值。
04为什么这个方法成立
- 任一合法解按是否选择最后一间分为两类。
- 选最后一间时,剩余部分必是前 i−2 间的合法解,最优可替换为 dp[i−2]。
- 按 i 递增,依赖已算好,归纳得到全局最优。
05把推导翻译成代码
Python · 可独立运行的教学实现
def non_adjacent_sum(a):
older = previous = 0
for value in a:
current = max(previous, older + value)
older, previous = previous, current
return previous逐个理解关键决定
older + value- 只能接前两间之前的最优值,不能接 previous。
older, previous = previous, current- 同时前移,避免先覆盖旧 previous 导致依赖混乱。
06时间、空间与实现范围
n 个状态、每状态两种选择,时间 O(n),只求最优值时辅助空间 O(1)。
恢复具体选择要保存信息或重新计算,不能声称同样代码能直接给出路径。
07改变条件,检查哪里会出错
状态定义为第 i 间金额却使用前缀转移
单个元素值与前缀最优是不同对象,要先把一句话定义写完整。
把不可达状态初始化成合法的0
最大值、最小值、计数问题的不可达表示不同,应选 −∞、+∞ 或0等对应语义。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[5,1,1,5] 的答案?
需要一点提示
两端不相邻。
查看解析与答案
10,选择第 1 与第 4 间。
[-2,-1] 本实现返回什么?
需要一点提示
允许空选择。
查看解析与答案
0;若必须选一间,则答案应为 −1,需要改状态约定。
首尾也相邻的环形版本怎么做?
需要一点提示
最优解不可能同时选首尾。
查看解析与答案
分别求去掉首元素、去掉尾元素的线性问题,取较大值;单元素另处理。