《Hello 算法》动态规划问题特征深度解析：识别最优子结构与无后效性

动态规划并非“套公式就能解”的模板算法，能否适用取决于问题本身是否具备两项关键特征——最优子结构（Optimal Substructure） 与 无后效性（No Aftereffects）。本篇基于《Hello 算法》动态规划问题特征一章展开，结合仓库中十余种语言的真实实现代码，从“爬楼梯最小代价”“带约束爬楼梯”两个递进式案例出发，讲透这两大特征的判定方法、状态定义技巧与代码落地路径。读完本文，你将能够独立判断一个最优化问题是否可以用动态规划求解，并在状态不满足无后效性时，通过扩充状态维度将问题“改造”回可解形态。

为什么先谈问题特征，再谈解法

在进入具体案例前，需要先厘清动态规划与另外两种主流“分而治之”思想的关系。子问题分解是一类通用的算法范式，但它在分治、动态规划与回溯三大算法中的侧重完全不同，原文档对此给出了清晰的三分法对照：

算法范式	子问题关系	求解方式	关注重点
分治（Divide and Conquer）	相互独立	递归切分到最小子问题，回溯时合并子问题解	子问题无重叠、结果可合并
动态规划（Dynamic Programming）	相互依赖、大量重叠	先解最小子问题，自底向上逐步推导	重叠子问题 + 最优子结构 + 无后效性
回溯（Backtracking）	由决策序列展开	试错枚举全部候选，用剪枝去掉无效分支	可行解的枚举与剪枝

动态规划常用于求解最优化问题。原文档明确指出：适合 DP 的最优化问题除了包含重叠子问题之外，通常还具备两大特征——最优子结构与无后效性。下面逐一通过改编后的爬楼梯问题展开。

特征一：最优子结构——以“爬楼梯最小代价”为例

问题改造：从计数问题升级为最优化问题

原文档对基础爬楼梯问题做了一处“微小改造”，使其更适合演示最优子结构：

爬楼梯最小代价：给定一个楼梯，你每次可以上 1 阶或 2 阶，每一阶都标有一个非负整数，代表踏上该阶梯需要付出的代价。给定一个非负整数数组 cost，其中 cost[i] 表示第 i 阶的代价，cost[0] 为地面（起点）。请问你最少需要花多少代价才能到达顶部？

假设第 1、2、3 阶的代价分别为 1、10、1，那么从地面爬到第 3 阶的最小代价是 2，对应路径为 0 → 1 → 3（先跳 1 阶踩上第 1 阶花费 1，再跳 2 阶直接落到第 3 阶花费 1）。

状态转移方程与最优子结构的含义

设 dp[i] 为爬到第 i 阶累计花费的最小代价。由于第 i 阶只能来自第 i-1 阶或第 i-2 阶（分别对应最后一步跳 1 阶或跳 2 阶），因此 dp[i] 只能等于 dp[i-1] + cost[i] 或 dp[i-2] + cost[i]。要想总代价最小，就取二者之中更小的那一个，于是得到状态转移方程：

$$dp[i] = \min(dp[i-1], dp[i-2]) + cost[i]$$

原文档由此引出了最优子结构的核心定义：原问题的最优解由子问题的最优解构造而来。具体到本例，我们是从 dp[i-1]、dp[i-2] 这两个子问题的最优解中挑出较优者，用它构造出原问题 dp[i] 的最优解。

原文档还指出了一个非常精妙的观察：普通爬楼梯问题求的是“方案数量”，看似是计数问题；可一旦把问题改成“求最多方案数”，会发现前后两个问题等价，最优子结构却悄然出现——第 n 阶的最大方案数等于第 n-1 阶与第 n-2 阶的最大方案数之和。这说明最优子结构的解读相当灵活，在不同问题中有不同含义，不能机械套用。

代码落地：DP 表版本与空间压缩版本

根据状态转移方程以及初始状态 dp[1] = cost[1]、dp[2] = cost[2]，即可写出动态规划代码。仓库中所有语言（Python、Java、C++、C、C#、Go、Rust、TS、JS、Kotlin、Swift、Dart、Ruby、Zig 等）均已提供完整可运行实现，以下为 en/codes/python/chapter_dynamic_programming/min_cost_climbing_stairs_dp.py 的核心逻辑：

def min_cost_climbing_stairs_dp(cost: list[int]) -> int:
    """Minimum cost climbing stairs: Dynamic programming"""
    n = len(cost) - 1
    if n == 1 or n == 2:
        return cost[n]
    # Initialize dp table, used to store solutions to subproblems
    dp = [0] * (n + 1)
    # Initial state: preset the solution to the smallest subproblem
    dp[1], dp[2] = cost[1], cost[2]
    # State transition: gradually solve larger subproblems from smaller ones
    for i in range(3, n + 1):
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
    return dp[n]

对照仓库中的 Java 实现 en/codes/java/chapter_dynamic_programming/min_cost_climbing_stairs_dp.java 可以看到，核心递推 dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i] 与 Python 版完全同构，两种语言在“初始化最小子问题 → 自底向上转移 → 返回 dp[n]”这三个阶段上保持一致，这正是所有语言实现共享的解题骨架：

public static int minCostClimbingStairsDP(int[] cost) {
    int n = cost.length - 1;
    if (n == 1 || n == 2)
        return cost[n];
    // 初始化 dp 表，用于存储子问题的解
    int[] dp = new int[n + 1];
    // 初始状态：预设最小子问题的解
    dp[1] = cost[1];
    dp[2] = cost[2];
    // 状态转移：从较小子问题逐步求解较大子问题
    for (int i = 3; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return dp[n];
}

下图展示了上述代码的完整 DP 递推过程，其中每个 dp[i] 都由前两个状态的最小值叠加 cost[i] 得到：

原文档特别强调：由于递推过程中 dp[i] 只依赖 dp[i-1] 与 dp[i-2] 这两个“紧邻”状态，本问题还可以做空间优化，把一维数组压缩成两个滚动变量，空间复杂度从 O(n) 降到 O(1)。仓库代码中以 _comp 结尾的函数即为此版本：

def min_cost_climbing_stairs_dp_comp(cost: list[int]) -> int:
    """Minimum cost climbing stairs: Space-optimized dynamic programming"""
    n = len(cost) - 1
    if n == 1 or n == 2:
        return cost[n]
    a, b = cost[1], cost[2]
    for i in range(3, n + 1):
        a, b = b, min(a, b) + cost[i]
    return b

从源码结构看（例如 min_cost_climbing_stairs_dp.c、_comp 与 Java 版 minCostClimbingStairsDPComp），a 与 b 分别滚动扮演 dp[i-2] 与 dp[i-1] 的角色，循环结束后 b 即 dp[n]。这是“只依赖少量邻近状态”型 DP 的通用降维手法，在后续章节（如背包问题、编辑距离问题）中会反复出现。如果你尚未掌握 DP 表格法与状态转移的基本套路，建议先阅读动态规划初探一节。

特征二：无后效性——从失效的状态转移说起

定义与正面示例

无后效性是让动态规划能够高效求解的重要特征之一，其定义为：给定某一状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。

仍以爬楼梯为例：给定状态 i，它未来只会发展到 i+1 与 i+2，分别对应跳 1 阶与跳 2 阶。做这两个选择时无需考察 i 之前的任何状态，因为过去对 i 的未来没有任何影响——这就是无后效性。

反例一：连续约束破坏无后效性

原文档接着抛出了一个关键变体——当约束被加上时，情况彻底改变：

带约束爬楼梯：给定一个共有 n 阶的楼梯，你每次可以上 1 阶或 2 阶，但不能连续两轮都跳 1 阶。请问共有多少种方案可以爬到楼顶？

以爬到第 3 阶为例，可行的方案只剩 2 种：0 → 1 → 3（跳 1 阶再跳 2 阶）与 0 → 2 → 3（跳 2 阶再跳 1 阶）。而连续三次跳 1 阶的路径 0 → 1 → 2 → 3 因违反约束被丢弃。

此时，“上一轮是否跳了 1 阶”这一历史信息，直接决定了本轮能否选择跳 1 阶。也就是说，下一次的选择无法仅由当前状态（当前所处台阶）决定，还必须依赖前一个状态（上一轮所跳的阶数）——无后效性被打破，原状态转移方程 dp[i] = dp[i-1] + dp[i-2] 也随之失效。原文档给出的解释非常直观：dp[i-1] 表示“本轮跳 1 阶”，但它内部混入了大量“上一轮已经跳过 1 阶”的方案，直接累加进 dp[i] 就会违反约束。

用“状态升维”重新满足无后效性

对策是扩充状态定义，把“丢掉的记忆”显式收进状态里。原文档定义：状态 [i, j] 表示位于第 i 阶、且上一轮跳了 j 阶，其中 j ∈ {1, 2}。这个二维状态能有效区分“上一轮跳 1 阶”与“上一轮跳 2 阶”，从而确定当前状态从哪里来：

• 上一轮跳了 1 阶时，再上一轮只能跳 2 阶（否则就连续两轮跳 1 阶），即 dp[i, 1] 只能从 dp[i-1, 2] 转移而来；
• 上一轮跳了 2 阶时，再上一轮跳 1 阶或 2 阶均可，即 dp[i, 2] 可以从 dp[i-2, 1] 或 dp[i-2, 2] 转移而来。

于是状态转移方程组为：

$$\begin{cases} dp[i, 1] = dp[i-1, 2] \\ dp[i, 2] = dp[i-2, 1] + dp[i-2, 2] \end{cases}$$

最终的答案取 dp[n, 1] + dp[n, 2]，即两种“最后一步跳法”的方案数之和：

仓库中 en/codes/python/chapter_dynamic_programming/climbing_stairs_constraint_dp.py 的实现与上述推导一一对应，且非常值得留意它的初始状态设计：

def climbing_stairs_constraint_dp(n: int) -> int:
    """Climbing stairs with constraint: Dynamic programming"""
    if n == 1 or n == 2:
        return 1
    # Initialize dp table, used to store solutions to subproblems
    dp = [[0] * 3 for _ in range(n + 1)]
    # Initial state: preset the solution to the smallest subproblem
    dp[1][1], dp[1][2] = 1, 0
    dp[2][1], dp[2][2] = 0, 1
    # State transition: gradually solve larger subproblems from smaller ones
    for i in range(3, n + 1):
        dp[i][1] = dp[i - 1][2]
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
    return dp[n][1] + dp[n][2]

注意这里 dp[i][j] 中第二维 j 表示“上一轮跳了 j 阶”，因此 j=0 的列在代码中始终不被使用（只分配不赋值），二维数组第二维取 3 是为方便按下标 1、2 直接寻址。从仓库内其他语言（如 en/codes/go/chapter_dynamic_programming/climbing_stairs_constraint_dp.go）的实现可以推断，所有语言都沿用“按 j 分裂计数、末位相加”这一统一结构，也说明把不满足无后效性的问题“升维”成满足无后效性的状态机，是动态规划建模中的通用修复手段。

另外，原文档给出的第 1、2 阶初始状态 dp[1][1]=1, dp[1][2]=0 与 dp[2][1]=0, dp[2][2]=1 也解释了“为什么直接爬到第 1 阶、第 2 阶的合法方案各只有 1 种”这一边界事实，是求解任何状态机型 DP 时必须小心处理的细节。

反例二：严重后效性导致 DP 失效

升维并非万能。原文档接着构造了一个“后效性严重”的问题：

带障碍生成的爬楼梯：给定一个共有 n 阶的楼梯，你每次可以上 1 阶或 2 阶。每当到达第 i 阶时，系统会自动在第 2i 阶生成一个障碍物，之后的任何轮次都不允许跳到第 2i 阶。例如，前两轮跳到第 2 阶和第 3 阶后，之后就不能再跳到第 4 阶和第 6 阶。请问共有多少种方案可以爬到楼顶？

在这个问题中，每一步选择都会在更高的台阶上生成新的障碍，进而影响之后所有轮次的可行选择。下一次跳法取决于全部过去状态——后效性无法通过有限的“升维”消除（因为你不知道未来会被哪些障碍封锁）。对于这类问题，原文档明确指出：动态规划往往难以求解。

后效性失效之后的出路

很多复杂的组合优化问题本质上都不满足无后效性，典型代表就是旅行商问题（Traveling Salesman Problem）。原文档给出了务实的工程结论：对这类问题，我们通常放弃精确最优解，转而在有限时间内获取“可用的局部最优解”，常用的方法包括：

• 启发式搜索：依赖领域知识设计的搜索规则，在可接受代价内逼近较优解；
• 遗传算法：通过选择、交叉、变异模拟自然进化，在多峰搜索空间中寻优；
• 强化学习：把求解过程建模为智能体与环境的序贯决策，用试错信号逐步优化策略。

这些方法在《Hello 算法》当前版本中不属于动态规划章节的展开范围，但它们共同说明了一个判断准则：拿到一个最优化问题，先检查是否具备重叠子问题、最优子结构与无后效性；前两条不满足或状态无法有限扩张，就要果断转向其他算法范式。

小结：一套可操作的 DP 适用性判定清单

综合原文档与仓库实现，可以将“一个最优化问题是否适合用动态规划”浓缩为以下三步自查：

1. 是否存在重叠子问题：递归展开后，是否反复求解相同的子问题？（这是分治与 DP 的分水岭。）
2. 是否具备最优子结构：原问题的最优解，能否由子问题的最优解构造出来？（参考“最小代价”与“最大方案数”的等价改造示例。）
3. 是否满足无后效性：未来演化是否只依赖当前状态？若答案是否定的，先尝试扩充状态定义（如把 dp[i] 扩展为 dp[i, j]）来吸收历史信息；若历史影响无法在有限状态内表达，则 DP 通常不再适用，应考虑启发式搜索等替代方案。

其中，特征二的可修复程度决定了问题难度：只需多考虑一个前驱状态时（如“不能连续跳 1 阶”），靠升维即可化解；而后效性蔓延到全部历史时（如“到达即生成障碍”），问题性质就发生了质变。掌握这套判定流程，再配合仓库中各章的实现代码反复对照，就能建立起“先判特征、再写转移方程、最后实现与降维”的标准解题动作。如果你希望继续深入，下一步可以阅读动态规划解题思路，学习从问题到状态定义再到转移方程的完整建模流程。