数据结构与算法（十）：动态规划与贪心算法

参考引用

• Hello 算法
• Github：hello-algo

1. 动态规划算法

• 动态规划将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率

问题：给定一个共有 n 阶的楼梯，你每步可以上 1 阶或者 2 阶，请问有多少种方案可以爬到楼顶？

• 下图所示，对于一个 3 阶楼梯，共有 3 种方案可以爬到楼顶

• 本题的目标是求解方案数量，可以考虑通过回溯来穷举所有可能性。具体来说，将爬楼梯想象为一个多轮选择的过程：从地面出发，每轮选择上 1 阶或 2 阶，每当到达楼梯顶部时就将方案数量加 1，当越过楼梯顶部时就将其剪枝

  /* 回溯 */
  void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
      // 当爬到第 n 阶时，方案数量加 1
      if (state == n)
          res[0]++;
      // 遍历所有选择
      for (auto &choice : choices) {
          // 剪枝：不允许越过第 n 阶
          if (state + choice > n)
              break;
          // 尝试：做出选择，更新状态
          backtrack(choices, state + choice, n, res);
          // 回退
      }
  }
  
  /* 爬楼梯：回溯 */
  int climbingStairsBacktrack(int n) {
      vector<int> choices = {1, 2}; // 可选择向上爬 1 或 2 阶
      int state = 0;                // 从第 0 阶开始爬
      vector<int> res = {0};        // 使用 res[0] 记录方案数量
      backtrack(choices, state, n, res);
      return res[0];
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

1.1 方法一：暴力搜索

• 回溯算法通常并不显式地对问题进行拆解，而是将问题看作一系列决策步骤，通过试探和剪枝，搜索所有可能的解。可以尝试从问题分解的角度分析这道题。设爬到第 $i$ 阶共有 $dp[i]$ 种方案，那么 $dp[i]$ 就是原问题，其子问题包括

$$dp[i-1],dp[i-2],\dots ,dp[2],dp[1]$$

• 由于每轮只能上 1 阶或 2 阶，因此当站在第 i 阶楼梯上时，上一轮只可能站在第 i-1 阶或第 i-2 阶上。换句话说，只能从第 i-1 阶或第 i-2 阶前往第 i 阶
  • 由此便可得出一个重要推论：爬到第 i-1 阶的方案数加上爬到第 i-2 阶的方案数就等于爬到第 i 阶的方案数
  • 在爬楼梯问题中，各子问题之间存在递推关系，原问题的解可以由子问题的解构建得来，下图展示了该递推关系

$$dp[i]=dp[i-1]+dp[i-2]$$

• 可以根据递推公式得到暴力搜索解法
  • 以 $dp[n]$ 为起始点，递归地将一个较大问题拆解为两个较小问题的和，直至到达最小子问题 $dp[1]$ 和 $dp[2]$ 时返回。其中，最小子问题的解是已知的，即 $dp[1]=1$、$dp[2]=2$，表示爬到第 1、2 阶分别有 1、2 种方案

  /* 搜索 */
  int dfs(int i) {
      // 已知 dp[1] 和 dp[2] ，返回之
      if (i == 1 || i == 2)
          return i;
      // dp[i] = dp[i-1] + dp[i-2]
      int count = dfs(i - 1) + dfs(i - 2);
      return count;
  }
  
  /* 爬楼梯：搜索 */
  int climbingStairsDFS(int n) {
      return dfs(n);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

• 下图展示了暴力搜索形成的递归树。对于问题 $dp[n]$，其递归树的深度为 n，时间复杂度为 $O(2^n)$
  • 指数阶属于爆炸式增长，如果输入一个比较大的 n，则会陷入漫长的等待之中
  • 指数阶的时间复杂度是由于 “重叠子问题” 导致的，以此类推，子问题中包含更小的重叠子问题，子子孙孙无穷尽也，绝大部分计算资源都浪费在这些重叠的问题上

1.2 方法二：记忆化搜索

• 为了提升算法效率，希望所有的重叠子问题都只被计算一次。为此，声明一个数组 mem 来记录每个子问题的解，并在搜索过程中将重叠子问题剪枝
  • 当首次计算 $dp[i]$ 时，将其记录至 mem[i]，以便之后使用
  • 当再次需要计算 $dp[i]$ 时，便可直接从 mem[i] 中获取结果，从而避免重复计算该子问题

  /* 记忆化搜索 */
  int dfs(int i, vector<int> &mem) {
      // 已知 dp[1] 和 dp[2] ，返回之
      if (i == 1 || i == 2)
          return i;
      // 若存在记录 dp[i] ，则直接返回之
      if (mem[i] != -1)
          return mem[i];
      // dp[i] = dp[i-1] + dp[i-2]
      int count = dfs(i - 1, mem) + dfs(i - 2, mem);
      // 记录 dp[i]
      mem[i] = count;
      return count;
  }
  
  /* 爬楼梯：记忆化搜索 */
  int climbingStairsDFSMem(int n) {
      // mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
      vector<int> mem(n + 1, -1);
      return dfs(n, mem);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 下图所示，经过记忆化处理后，所有重叠子问题都只需被计算一次，时间复杂度被优化至 O(n)
  • 记忆化搜索是一种 “从顶至底” 的方法，从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯将子问题的解逐层收集，构建出原问题的解

1.3 方法三：动态规划

• 动态规划是一种 “从底至顶” 的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解
  • 由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，初始化一个数组 dp 来存储子问题的解

  /* 爬楼梯：动态规划 */
  int climbingStairsDP(int n) {
      if (n == 1 || n == 2)
          return n;
      // 初始化 dp 表，用于存储子问题的解
      vector<int> dp(n + 1);
      // 初始状态：预设最小子问题的解
      dp[1] = 1;
      dp[2] = 2;
      // 状态转移：从较小子问题逐步求解较大子问题
      for (int i = 3; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

根据以上内容，总结出动态规划的常用术语

• 将数组 $dp$ 称为 $dp$ 表，$dp[i]$ 表示状态 $i$ 对应子问题的解
• 将最小子问题对应的状态（即第 1 和 2 阶楼梯）称为初始状态
• 将递推公式 $dp[i]=dp[i-1]+dp[i-2]$ 称为状态转移方程

1.4 空间优化

• 由于 $dp[i]$ 只与 $dp[i-1]$ 和 $dp[i-2]$ 有关，因此无须使用一个数组 dp 来存储所有子问题的解，而只需两个变量滚动前进即可

  /* 爬楼梯：空间优化后的动态规划 */
  // 空间复杂度从 O(n) 降低至 O(1)
  int climbingStairsDPComp(int n) {
      if (n == 1 || n == 2)
          return n;
      int a = 1, b = 2;
      for (int i = 3; i <= n; i++) {
          int tmp = b;
          b = a + b;
          a = tmp;
      }
      return b;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时可以只保留必要的状态，通过 “降维” 来节省内存空间，这种空间优化技巧被称为 “滚动变量” 或 “滚动数组”

2. 贪心算法

• 贪心算法是一种常见的解决优化问题的算法，其基本思想是：在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期望获得全局最优解

• 贪心算法和动态规划都常用于解决优化问题，它们之间的区别如下

  • 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解
  • 贪心算法不会重新考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决

问题：给定 n 种硬币，第 i 种硬币的面值为 coins[i-1]，目标金额为 amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币个数，如果无法凑出目标金额则返回 -1

/* 零钱兑换：贪心 */
int coinChangeGreedy(vector<int> &coins, int amt) {
    // 假设 coins 列表有序
    int i = coins.size() - 1;
    int count = 0;
    // 循环进行贪心选择，直到无剩余金额
    while (amt > 0) {
        // 找到小于且最接近剩余金额的硬币
        while (i > 0 && coins[i] > amt) {
            i--;
        }
        // 选择 coins[i]
        amt -= coins[i];
        count++;
    }
    // 若未找到可行方案，则返回 -1
    return amt == 0 ? count : -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.1 贪心算法优缺点

• 贪心算法不仅操作直接、实现简单，而且通常效率也很高。在以上代码中，记硬币最小面值为 $min(coins)$，则贪心选择最多循环 $amt/min(coins)$ 次，时间复杂度为 $O(amt/min(coins))$。这比动态规划解法的时间复杂度 $O(n\ast amt)$ 提升了一个数量级

• 然而，对于某些硬币面值组合，贪心算法并不能找到最优解

  • 正例 $coins=[1,5,10,20,50,100]$：在该硬币组合下，给定任意 $amt$，贪心算法都可以找出最优解
  • 反例 1 $coins=[1,20,50]$：假设 $amt=60$，贪心算法只能找到 $50+1\times 10$ 的兑换组合，共计 11 枚硬币，但动态规划可以找到最优解 $20+20+20$，仅需 3 枚硬币
  • 反例 2 $coins=[1,49,50]$：假设 $amt=98$，贪心算法只能找到 $50+1\times 48$ 的兑换组合，共计 49 枚硬币，但动态规划可以找到最优解 $49+49$，仅需 2 枚硬币

• 一般情况下，贪心算法适用于以下两类问题
  • 可以保证找到最优解：贪心算法在这种情况下往往是最优选择，因为它往往比回溯、动态规划更高效
  • 可以找到近似最优解：对于很多复杂问题来说，寻找全局最优解是非常困难的，能以较高效率找到次优解也是非常不错的

2.2 贪心典型例题

• 硬币找零问题
  • 在某些硬币组合下，贪心算法总是可以得到最优解
• 区间调度问题
  • 假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解
• 分数背包问题
  • 给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解
• 股票买卖问题
  • 给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润
• 霍夫曼编码
  • 霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率最小的两个节点合并，最后得到的霍夫曼树的带权路径长度（即编码长度）最小
• Dijkstra 算法
  • 它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法