专题进阶 · 动态规划推荐总顺序 · 第 64 / 148 课

先定义前缀状态,再按最后一个选择推导最大不相邻子序列和。

先学会这些,再进入本课 DP 思想
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

一维 DP1D DP

用一个索引表达状态,常按长度、位置或容量推进。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

先定义前缀状态,再按最后一个选择推导最大不相邻子序列和。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 任一合法解按是否选择最后一间分为两类。
  2. 选最后一间时,剩余部分必是前 i−2 间的合法解,最优可替换为 dp[i−2]。
  3. 按 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[5,1,1,5] 的答案?

需要一点提示

两端不相邻。

查看解析与答案

10,选择第 1 与第 4 间。

练习 2 · 边界与辨析

[-2,-1] 本实现返回什么?

需要一点提示

允许空选择。

查看解析与答案

0;若必须选一间,则答案应为 −1,需要改状态约定。

练习 3 · 变式与迁移

首尾也相邻的环形版本怎么做?

需要一点提示

最优解不可能同时选首尾。

查看解析与答案

分别求去掉首元素、去掉尾元素的线性问题,取较大值;单元素另处理。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。