掌握动态规划的20种模式

动态规划（DP）可以说是编程面试中最难的话题。不过，和其他任何话题一样，学习它的最快方法是理解不同的模式，这些模式能帮助你解决各种各样的问题。

在本文中，我将带你了解20种模式，这些模式会让学习动态规划变得容易得多。我会分享每种模式的使用场景，并提供力扣（LeetCode）上的练习题链接，以便你能更好地学习。我按照从易到难的顺序列出了这些模式，还附上了学习每种模式的参考资源链接。

1. 斐波那契数列模式：即Fibonacci Sequence，当一个问题的解决方案依赖于相同问题的较小实例的解决方案时，斐波那契数列模式就很有用。存在一种清晰的递归关系，通常类似于经典的斐波那契数列公式 $F(n)=F(n-1)+F(n-2)$。
   

   • 力扣题目：
     • 力扣70题：爬楼梯
     • 力扣509题：斐波那契数
     • 力扣746题：使用最小花费爬楼梯

2. 卡登算法（Kadane’s Algorithm）：卡登算法主要用于解决最大子数组问题及其变体，这类问题要求在一维数字数组中优化一个连续的子数组。
   

   • 力扣题目：
     • 力扣53题：最大子数组和
     • 力扣918题：环形子数组的最大和
     • 力扣152题：乘积最大子数组

3. 0/1背包模式：即0/1 Knapsack，当出现以下情况时，0/1背包模式很有用：
   

   • 你有一组物品，每个物品都有重量和价值。
   • 你需要从这些物品中选择一个子集。
   • 你能使用的总重量（或其他资源）存在限制。
   • 你想最大化（或最小化）所选物品的总价值。
   • 每个物品只能选择一次（因此称为 “0/1”，即你要么选它，要么不选）。
   • 力扣题目：
     • 力扣416题：分割等和子集
     • 力扣494题：目标和
     • 力扣1049题：最后一块石头的重量 II

4. 完全背包模式：即Unbounded Knapsack，当出现以下情况时，完全背包模式很有用：

   • 你有一组物品，每个物品都有重量和价值。
   • 你需要选择物品以最大化总价值。
   • 你能使用的总重量（或其他资源）存在限制。
   • 你可以多次选择每个物品（与0/1背包不同，0/1背包中每个物品只能选择一次）。
   • 每个物品的供应被视为是无限的。
   • 力扣题目：
     • 力扣322题：零钱兑换
     • 力扣518题：零钱兑换 II
     • 力扣279题：完全平方数

5. 最长公共子序列（LCS）模式：即Longest Common Subsequence，当你得到两个序列，并且需要找到一个在这两个给定序列中都按相同顺序出现的子序列时，最长公共子序列模式就很有用。
   

   • 力扣题目：
     • 力扣1143题：最长公共子序列
     • 力扣583题：两个字符串的删除操作
     • 力扣1092题：最短公共超序列

6. 最长递增子序列（LIS）模式：即Longest Increasing Subsequence，最长递增子序列模式用于解决涉及在一个序列中找到元素按递增顺序排列的最长子序列的问题。
   

   • 力扣题目：
     • 力扣300题：最长递增子序列
     • 力扣673题：最长递增子序列的个数
     • 力扣354题：俄罗斯套娃信封问题

7. 回文子序列模式：即Palindromic Subsequence，当解决涉及在一个序列（通常是字符串）中找到一个正向和反向读取都相同的子序列的问题时，回文子序列模式很有用。
   

   • 力扣题目：
     • 力扣516题：最长回文子序列
     • 力扣647题：回文子串
     • 力扣1312题：让字符串成为回文串的最少插入次数

8. 编辑距离模式：即Edit Distance，编辑距离模式用于解决涉及使用最少操作次数将一个序列（通常是字符串）转换为另一个序列的问题。允许的操作通常包括插入、删除和替换。

   • 力扣题目：
     • 力扣72题：编辑距离
     • 力扣583题：两个字符串的删除操作
     • 力扣712题：两个字符串的最小ASCII删除和

9. 子集和模式：即Subset Sum，子集和模式用于解决需要确定给定集合中的元素子集是否能求和达到特定目标值的问题。

   • 力扣题目：
     • 力扣416题：分割等和子集
     • 力扣494题：目标和
     • 力扣698题：划分为k个相等的子集

10. 字符串分割模式：即String Partition，字符串分割模式用于解决涉及将一个字符串分割成满足特定条件的较小子字符串的问题。当出现以下情况时，它很有用：

    • 你在处理涉及字符串或序列的问题。
    • 问题要求将字符串分割成子字符串或子序列。
    • 你需要在这些分割上优化某些属性（例如，最小化成本、最大化价值）。
    • 整个问题的解决方案可以由较小子字符串的子问题解决方案构建而成。
    • 需要考虑字符串的不同分割方式。
    • 力扣题目：
      • 力扣139题：单词拆分
      • 力扣132题：分割回文串 II
      • 力扣472题：连接词

11. 卡特兰数模式：即Catalan Numbers，卡特兰数模式用于解决可以分解为更小、相似子问题的组合问题。这种模式的一些应用场景包括：

    • 计算给定长度的有效括号表达式的数量。
    • 计算由 n 个节点可以形成的不同二叉搜索树的数量。
    • 计算将有 n+2 条边的多边形三角剖分的方法数量。
    • 力扣题目：
      • 力扣96题：不同的二叉搜索树
      • 力扣22题：括号生成

12. 矩阵链乘法模式：即Matrix Chain Multiplication，这种模式用于解决涉及确定操作的最优顺序以最小化一系列操作成本的问题。它基于著名的优化问题：矩阵链乘法。当出现以下情况时，它很有用：

    • 你在处理可以两两组合的元素序列。
    • 组合元素的成本取决于组合的顺序。
    • 你需要找到组合元素的最优方法。
    • 问题涉及最小化（或最大化）组合元素的操作成本。
    • 力扣题目：
      • 力扣1039题：多边形三角剖分的最低得分
      • 力扣312题：戳气球
      • 力扣1000题：合并石头的最低成本

13. 计算不同方式模式：即Count Distinct Ways，当出现以下情况时，这种模式很有用：

    • 你需要计算实现某个目标或达到特定状态的不同方式的数量。
    • 问题涉及通过一系列选择或步骤来达到目标。
    • 有多种有效的路径或组合可以达到解决方案。
    • 问题可以分解为具有重叠解决方案的较小子问题。
    • 你在处理询问 “有多少种方式” 可以完成某事的组合问题。
    • 力扣题目：
      • 力扣91题：解码方法
      • 力扣2266题：统计打字方案数

14. 网格上的动态规划模式：即DP on Grids，网格上的动态规划模式用于解决涉及在网格（二维数组）中导航或优化路径的问题。对于这些问题，你需要考虑多个移动方向（例如，向右、向下、对角线），并且每个单元格的解决方案取决于相邻单元格的解决方案。

    • 力扣题目：
      • 力扣62题：不同路径
      • 力扣64题：最小路径和
      • 力扣329题：矩阵中的最长递增路径

15. 树上的动态规划模式：即DP on Trees，当出现以下情况时，树上的动态规划模式很有用：

    • 你在处理由节点和边表示的树结构数据。
    • 问题可以分解为本身也是树问题的子问题的解决方案。
    • 问题要求在每个节点上做出影响其孩子或父节点的决策。
    • 你需要根据节点的孩子或祖先计算节点的值。
    • 力扣题目：
      • 力扣337题：打家劫舍 III
      • 力扣124题：二叉树中的最大路径和
      • 力扣968题：监控二叉树

16. 图上的动态规划模式：即DP on Graphs，当出现以下情况时，图上的动态规划模式很有用：

    • 你在处理涉及图结构的问题。
    • 问题要求在图上找到最优路径、最长路径、环或其他优化属性。
    • 你需要根据节点或边的邻居或连接组件计算它们的值。
    • 问题涉及在遍历图的同时维护某种状态。
    • 力扣题目：
      • 力扣787题：K站中转内最便宜的航班
      • 力扣1334题：阈值距离内邻居最少的城市

17. 数位动态规划模式：即Digit DP，当出现以下情况时，数位动态规划模式很有用：

    • 你在处理涉及对一定范围内的数字进行计数或求和的问题。
    • 问题要求单独考虑数字的每一位。
    • 你需要找到与范围内数字的数位相关的模式或属性。
    • 数字范围很大（通常高达 $10^{18}$ 或更大），使得暴力解法不可行。
    • 问题涉及对数位的限制。
    • 力扣题目：
      • 力扣357题：统计各位数字都不同的数字个数
      • 力扣233题：数字 1 的个数
      • 力扣902题：最大为 N 的数字组合

18. 位掩码动态规划模式：即Bitmasking DP，位掩码动态规划模式用于解决涉及大量状态或组合的问题，其中每个状态可以使用整数中的位有效地表示。当出现以下情况时，它特别有用：

    • 你在处理涉及元素子集或组合的问题。
    • 元素的总数相对较少（通常 <= 20 - 30）。
    • 你需要有效地表示和操作元素集合。
    • 问题涉及对每个元素做出决策（包含/排除）或跟踪已访问/未访问的状态。
    • 你希望在动态规划解决方案中优化空间使用。
    • 力扣题目：
      • 力扣1986题：完成任务的最少工作时间段
      • 力扣2305题：公平分发饼干
      • 力扣847题：访问所有节点的最短路径

19. 概率动态规划模式：即Probability DP，当出现以下情况时，这种模式很有用：

    • 你在处理涉及概率计算的问题。
    • 一个状态的概率取决于先前状态的概率。
    • 你需要计算某个结果的期望值。
    • 问题涉及随机过程或机会游戏。
    • 力扣题目：
      • 力扣688题：骑士在棋盘上的概率
      • 力扣808题：分汤
      • 力扣837题：新21点

20. 状态机动态规划模式：即State Machine DP，当出现以下情况时，状态机动态规划模式很有用：

    • 问题可以建模为一系列状态以及这些状态之间的转换。
    • 从一个状态转移到另一个状态有明确的规则。
    • 最优解决方案取决于做出最佳的状态转移序列。
    • 问题涉及做出影响未来状态的决策。
    • 可能的状态数量是有限的，并且每个状态都可以明确定义。
    • 力扣题目：
      • 力扣309题：最佳买卖股票时机含冷冻期
      • 力扣123题：买卖股票的最佳时机 III