外观
动态规划三步拆解实测：状态定义、转移方程与滚动数组省内存九成
动态规划题的挫败感很有共性：看题解时每一行都懂，自己动笔时状态定义不出来、转移方程写不顺、边界条件漏一半。问题通常不在数学能力，而在没有一个固定的推导流程——大多数人试图「凭感觉想出方程」，而成熟的写法是机械地走三步：先从最后一步倒推出状态该记什么，再按决策枚举写转移，最后按依赖关系定初始化和遍历顺序。流程走通，方程是推导出来的，不是灵光一现猜出来的。
这篇文章用三道递进的实际题目走完整个流程：打家劫舍演示「状态定义决定一切」，零钱兑换演示「转移方程的枚举写法」，背包问题演示「滚动数组如何把二维压成一维」。所有代码给出可运行的 Python 实现，并附上每一步的空间优化理由。
第一步：状态定义要从「最后一步」倒推
状态定义是动态规划的全部地基，而推导它的可靠入口是问一个固定问题：问题的最后一步在做什么？ 打家劫舍问「一排房屋能偷到的最大金额，不能偷相邻两家」——最后一步是面对最后一栋房屋，要么偷它（则倒数第二栋必须跳过），要么不偷它。这个决策立刻暴露出状态需要的信息：偷到第 i 栋时的最优解 depends on 前面栋数的最优解，于是状态自然定义为「考虑前 i 栋房屋能偷到的最大金额」。定义一旦这样落定，转移方程几乎是抄写性质的：
python
# 打家劫舍：状态定义 + 滚动变量优化（Python）
def rob(nums: list[int]) -> int:
# prev2 表示考虑前 i-2 栋的最优解，prev1 表示前 i-1 栋的最优解
prev2, prev1 = 0, 0
for amount in nums: # 从左到右逐栋决策
# 偷当前：prev2 + 当前金额；不偷：维持 prev1
prev2, prev1 = prev1, max(prev1, prev2 + amount)
return prev1 # 扫描结束，prev1 即全部房屋的最优解注意这里没有开 dp 数组：状态转移只依赖前两个状态，属于「滚动依赖」，用两个变量就够，空间 O(1)。这个优化不是事后聪明——三步流程走完后看一眼「转移依赖了几个状态」，依赖几个就留几个，这是滚动优化的通用判断标准，比背「打家劫舍用两个变量」的结论有用得多。
状态定义最常见的错误是「记录得太少」：比如只定义「偷到第 i 栋的最大值」而不区分第 i 栋偷没偷，转移时就丢失了「相邻约束」这条信息，方程写不出来。反过来也有定义得太多的：把与后续决策无关的信息塞进状态，维度爆炸。判断标准始终是同一条——状态必须携带写出转移方程所需的全部历史信息，且仅携带这些。
第二步与第三步：转移枚举与遍历顺序
零钱兑换问「凑出金额 amount 的最少硬币数，每种硬币无限用」。套三步流程：最后一步是「用了某枚硬币 coin 凑出 amount」，此前凑的是 amount − coin，于是状态定义为「凑出金额 x 的最少硬币数」，转移按「最后一枚硬币是哪种」枚举所有 coin，取最小：
python
# 零钱兑换：完全背包形态的最少硬币数（Python）
def coin_change(coins: list[int], amount: int) -> int:
INF = amount + 1 # 哨兵：不可能凑出的大数（不引入溢出风险）
dp = [INF] * (amount + 1) # dp[x]：凑出金额 x 的最少硬币数
dp[0] = 0 # 金额 0 需要零枚硬币，唯一确定的事实
for coin in coins: # 外层枚举硬币种类
for x in range(coin, amount + 1): # 内层正序：同种硬币可重复使用
if dp[x - coin] + 1 < dp[x]: # 用一枚 coin 是否更省
dp[x] = dp[x - coin] + 1
return dp[amount] if dp[amount] <= amount else -1 # 哨兵判断凑不出这段代码藏着动态规划最容易踩的遍历顺序问题。完全背包（硬币无限）内层正序，因为「用更少枚同种硬币凑 x」依赖本轮刚更新的 dp[x−coin]；而 0-1 背包（每件物品至多用一次）内层必须倒序——正序会让本轮刚更新的值反过来污染同一轮后面的更新，等价于同一件物品被重复装入。顺序不是玄学，是「转移依赖哪一轮的值」的直接后果：依赖上一轮就倒序压掉本轮依赖，依赖本轮就正序保留它。
时间复杂度上，零钱兑换是 O(n·amount)，n 为硬币种数；空间 O(amount)。这个复杂度在 amount 为 10⁴ 量级时轻松通过，也解释了为什么这类题目的数据范围总是把 amount 卡在十万以内——出题人默认的就是伪多项式解法。
滚动数组的完整案例：从二维背包到一维
0-1 背包问「n 件物品、容量 V 的背包，每件至多装一次，能装出的最大价值」。标准的二维状态是 dp[i][v]：考虑前 i 件物品、容量 v 时的最大价值。转移只依赖上一行：
python
# 0-1 背包：二维写法 → 一维滚动数组（Python）
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
n = len(weights)
# dp[i+1][v]：考虑前 i 件、容量 v 的最大价值；行数 n+1 省去 i-1 判负
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(n):
for v in range(capacity + 1):
dp[i + 1][v] = dp[i][v] # 不装第 i 件
if v >= weights[i]: # 装得下才考虑装
dp[i + 1][v] = max(dp[i + 1][v],
dp[i][v - weights[i]] + values[i])
return dp[n][capacity]
# 空间 O(nV)。观察：第 i+1 行只读第 i 行，且 v 只读更小的下标滚动优化的依据就写在上面的注释里：新行只依赖上一行，且依赖的列下标严格更小。因此可以用一维数组从大到小遍历容量——大下标先更新，它读到的小下标仍是「上一行」的值，恰好等价于二维语义：
python
# 0-1 背包一维优化版：内层倒序是正确性关键（Python）
def knapsack_optimized(weights: list[int], values: list[int], capacity: int) -> int:
dp = [0] * (capacity + 1) # dp[v] 复用为「上一行 + 当前行」的滚动数组
for w, val in zip(weights, values):
for v in range(capacity, w - 1, -1): # 倒序：保证 dp[v-w] 还是上一行的值
dp[v] = max(dp[v], dp[v - w] + val)
return dp[capacity] # 空间从 O(nV) 降到 O(V)一维版省掉了整个 n×V 的矩阵，在 n 和 V 都是几千的典型数据下，内存占用缩小约 n 倍——这就是标题里「省内存九成以上」的实际来源。同样的推导可以反过来验证遍历方向：把倒序改成正序，dp[v−w] 读到的已是「本轮装过一次」的值，0-1 背包悄悄变成完全背包，答案只会偏大不会报错，属于最隐蔽的一类错误。
方法论与避坑总结
- 状态定义写不出，先回到「最后一步」。描述最后一步的决策、决策前残留的问题规模，状态需要携带的信息会自动浮现；跳过这一步直接套模板，是「看得懂题解、写不出代码」的根源。
- 遍历顺序由依赖方向决定，不是背出来的。问自己一句「dp[x] 的转移读的是上一轮还是本轮的值」：读上一轮用倒序（0-1 背包），读本轮用正序（完全背包）；写完用两件物品的小用例手算验证，污染错误立刻现形。
- 初始化要与状态定义严格对齐。dp[0] = 0 表示「凑出金额 0 用零枚硬币」而非「没有金额」，「恰好装满」与「不超过容量」两种题面的初始化不同——前者非法状态置无穷、后者全部置零，混用会得到系统性偏移的答案。
- 滚动优化的前提是依赖的局部性。只有当转移只依赖常数个前序状态（或上一行的更小列下标）时才能滚动；先写清二维语义、验证正确，再压缩一维，两步分开做，出错时能回到二维版对照。
- 用「恰好 / 至少 / 至多」校准答案取值位置。求恰好凑出时答案是 dp[amount] 且需判断是否可达；求最多能装时答案是整个 dp 数组的最大值还是 dp[V] 取决于状态定义——这些取值规则都写在状态定义里，定义清楚则答案位置无歧义。
动态规划的可迁移能力不在题库量，而在流程稳定性：状态定义从最后一步倒推、转移按决策枚举、顺序按依赖确定、优化按依赖局部性压缩。四句话覆盖了绝大多数经典题目的推导路径，剩下的只是把流程在一道道题里练到肌肉记忆。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。