14.3   DP 解题思路 - Hello 算法

  1. 如何判断一个问题是不是动态规划问题？
  2. 求解动态规划问题该从何处入手，完整步骤是什么？

如何判断动态规划问题？

[!NOTE] DP三大特征
如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件，具体如下

  1. 先验条件：是否能用回溯（决策树）、DFS 暴力穷举？
  2. 加分项：
    • 问题目标是最优解（最大值/最小值）。
    • 状态转移可被公式化（如 dp[i] = dp[i-1] + ...）。
  3. 减分项：
    • 需要输出所有解（而非最优解）。动态规划通常会在求解过程中”压缩”或”丢弃”次优解，只保留最优解用于后续计算，保存所有解需要指数级空间
    • 明显属于排列组合问题（例如全排列）。

通过分析这三个特征，可以系统化判断一个问题是否适合动态规划。

动态规划的三个核心特征是重叠子问题、最优子结构和无后效性。以下通过具体例子和通俗解释说明它们的含义和区别：

1. 重叠子问题（Overlapping Subproblems）

  • 定义：在求解过程中，不同的问题会重复调用相同的子问题。动态规划通过缓存子问题的结果避免重复计算，提高效率。
  • 示例：计算斐波那契数列 fib(n) = fib(n-1) + fib(n-2)：
  • 递归树中存在大量重复节点（比如 fib(3) 被多次计算）。
    • 动态规划通过直接查表跳过重复计算。

2. 最优子结构（Optimal Substructure）

  • 定义：问题的最优解可以通过其子问题的最优解组合得到。必须保证通过子问题的最优解能直接推导出原问题的最优解。如果最后结果可能从次优子结构产生，那么则不适合DP，尤其是全局最优解不一定包含子问题的最优解的那些问题

  • 示例：最短路径问题（DP）：

    • 如果从节点 A 到 C 的最短路径是 A → B → C，那么 A → B 的路径也必须是 A 到 B 的最短路径（否则整体不是最短的）。
    • 反例：最长路径问题。
      例如，在环形图中，A → B → C → A 可以无限循环，无法直接通过子问题的解推导出全局最优解。

3. 无后效性（Non-aftereffect）

  • 定义：某一阶段的状态一旦确定，后续的决策不会影响之前的状态（未来的决策仅依赖于当前状态）。
  • 示例：经典的背包问题：
    • 状态 dp[i][w] 表示前 i 个物品在背包容量 w 下的最大价值。
    • 选择物品时，不管之前的物品如何放入（只关心当前剩余的容量），后续决策不会改变已选择的物品。
    • 反例：带有状态的依赖问题。
      例如，股票买卖问题中，如果交易次数会影响后续操作（如交易费），则不符合无后效性（需通过多维状态描述）。

4. 状态压缩（State Compression） 是动态规划中一种优化空间复杂度的技巧/思想。其核心思想是：

只保留对当前决策有影响的部分状态，丢弃无关或不再使用的历史状态。

三者的关系

特性 核心作用 示例问题 反例
重叠子问题 通过缓存子问题结果减少计算量 斐波那契数列 快速排序（无重叠）
最优子结构 保证全局最优解由局部最优解组合得到 最短路径、背包问题 最长路径问题
无后效性 确保未来决策与历史无关，简化状态转移方程 背包问题 有状态依赖的问题、需要维护具体路径或排列组合的方案，而DP通常只关心最优值，不关心具体路径

注意：路径只要是求一个最短路径，也可能是动态规划，许多动态规划问题可以通过逆向推导状态转移路径来恢复具体的解。这种方法通常被称为 “路径回溯” 或 **”解重构”**。

记忆化搜索 VS 动态规划

记忆化搜索和动态规划是解决重叠子问题的两种方法，后者在前者不管不顾的基础上，优化了空间复杂度，显式循环解决了递归，它们有以下主要区别：

  1. 实现方向
  • 记忆化搜索：自顶向下 (Top-down)，从原问题出发，通过递归调用解决子问题
  • 动态规划：自底向上 (Bottom-up)，从最小的子问题开始，逐步构建出原问题的解
  1. 状态转移方式
  • 记忆化搜索：通过函数的递归调用隐式地表达状态转移
  • 动态规划：显式地写出状态转移方程，通常使用循环实现
  1. 空间利用
  • 记忆化搜索：需要额外的递归调用栈空间
  • 动态规划：一般只需要 DP 数组空间，有时还可以进行空间优化
  1. 代码实现对比

记忆化搜索示例：

1
2
3
4
5
6
7
def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

动态规划示例：

1
2
3
4
5
6
7
8
def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
  1. 适用场景

  • 记忆化搜索：

    • 状态转移比较复杂的问题
    • 边界情况较多
    • 不是所有状态都需要计算
    • 需要快速实现时

  • 动态规划：

    • 状态转移规律明显
    • 需要求解所有状态
    • 对空间复杂度要求高
    • 需要优化性能时
  1. 性能比较
  • 记忆化搜索：可能会有函数调用开销，但只计算需要的状态
  • 动态规划：没有递归开销，但会计算所有可能的状态

选择建议：

  1. 如果问题的状态转移复杂，用记忆化搜索更容易实现
  2. 如果需要优化性能和空间，选择动态规划
  3. 在实际工程中，可以先用记忆化搜索实现，后续需要优化时再转换为动态规划