摘要：动态规划（Dynamic Programming，简称 DP）可以说是编程面试中最难掌握的一类算法，很多同学即便刷了不少题却依然不得其要领。

动态规划（Dynamic Programming，简称 DP）可以说是编程面试中最难掌握的一类算法，很多同学即便刷了不少题却依然不得其要领。

其实掌握动态规划最快的方式，是理解一些常见的解题模式。只要掌握了这些模式，就能举一反三，在新问题面前迅速识别出适用的套路，从而灵活应对。

本文总结了 20 种常见的动态规划解题模式，帮助大家更轻松地掌握这部分内容。同时每种模式都附上对应的 LeetCode 练习题，方便大家边学边练，加深理解。

当一个问题的解依赖于该问题的较小子问题的解时，斐波那契数列的解题模式就非常适用。

这类问题通常具有明显的递归关系，类似于经典的斐波那契公式：

每一步的结果由前两步的结果推导而来。

这些题目非常适合作为动态规划的入门练习，有助于理解状态转移的基本思想。

在掌握了斐波那契这种“由前几步推导当前结果”的基础模式后，我们可以进一步学习 Kadane 算法。

Kadane算法主要用于解决「最大子数组和」这类问题及其变种，其核心思想是在一维数组中找到某个连续子数组，使其值达到最大（或最优）。

实现时，可以通过一次遍历，不断维护「以当前位置为结尾的子数组的最优值」，进而推导出全局最优结果，这是动态规划思想一个非常经典的应用。

当遇到具备以下特点的问题时，可以考虑使用 0/1 背包的解题模式：

0/1 背包模式是动态规划中非常重要的基础模型，理解之后可以应对大量“子集选择 + 约束条件”的问题类型。

在理解了「0/1 背包」后，下面我们再来看看它的一个重要变种——完全背包问题。

当遇到以下类型的问题时，可以考虑使用完全背包的解题模式：

这类问题非常常见，尤其是在硬币找零、组合数等场景中，是背包问题中的一个重要变种。

完全背包模式非常适合解决“物品可重复使用”的优化类问题。

背包问题更多强调的是 “资源约束 + 最优选择”，而当问题转向 “比较两个序列之间的关系” 时，就会引出另一类重要的 DP 模式——最长公共子序列（LCS）。

当你面对两个序列（如字符串、数组等），需要找出一个在两个序列中都按顺序出现的子序列时，并且要求这个子序列尽可能长。就可以考虑使用最长公共子序列（LCS）模式来解决。

这类问题的关键点在于：在不改变元素相对顺序的前提下，寻找两个序列之间的最长“共同部分”。它常被应用于 字符串比对、差异检测、文件比较 等问题。

LCS 模式是字符串类动态规划问题的基础，掌握它能帮助我们解决一大类与「序列比较」相关的题目。

在掌握了 最长公共子序列（LCS） 之后，我们再来看另一类与“子序列”相关的经典问题——最长递增子序列（LIS）。

最长递增子序列模式适用于这类问题：在一个给定的序列中，找出一个元素严格递增的最长子序列，需要注意的是：

注意：这类问题除了经典的 DP 解法，还有进阶的二分查找优化方案（时间复杂度可降至 O(n log n)）。

回文子序列模式适用于这类问题：在一个序列（通常是字符串）中，找出一个正着读和反着读都一样的子序列或子串。

这类问题的关键点是利用动态规划找出符合“回文特性”的最优子结构，常见的题型包括：

编辑距离模式常用于这类问题：将一个序列（通常是字符串）转换成另一个序列，要求操作次数最少，这里的操作可以是：

前面我们介绍的模式大多集中在“序列问题”。接下来我们切换视角，来看一类和 集合选择 有关的动态规划问题——子集和。

子集和模式适用于这类问题：给定一组数，判断是否存在某个子集，它们的和刚好等于目标值。

这类问题的本质是“在选与不选之间做出决策”，因此通常使用动态规划 + 状态转移来解决，属于典型的 0/1 背包问题的变种。

子集和类问题在 集合划分、资源分配、背包选取 等场景中非常常见，是动态规划中非常重要的一类模式。

字符串切分模式适用于这类问题：将一个字符串划分成若干个满足特定条件的子串，并在所有可能的切分方式中，寻找最优解（如代价最小、次数最少或方案数最多）。

这类问题的特点包括：

这类问题的难点在于状态设计和转移逻辑，常借助区间动态规划（如 dp[i][j] 表示字符串某一段的最优值）来求解。

字符串切分是字符串动态规划的一个重要分支，尤其在处理“连续性 + 状态转移”的问题中非常高频。

卡特兰数是一类经典的组合数学问题，适用于将一个大问题拆解为多个结构相似的子问题的场景，它常常用来解决计数类问题，

这一模式常见于以下几类问题：

这个模式常用于解决一类“操作顺序优化”的问题，它的目标是：在给定的一组操作中，找到一种执行顺序，使得整体代价（如计算成本、时间复杂度等）最小。

这种模型通常适用于以下场景：

这类问题本质上属于区间型动态规划，需要枚举所有可能的划分方式，将大问题分解为子区间，再递归地求解子问题，从而得到全局最优解。

这种动态规划模式常用于解决“有多少种不同方式”可以达成某个目标的计数类问题。具体适用于以下几种情况：

这类题目大多采用一维 DP 数组来解决，其中 dp[i] 表示前 i 个元素有多少种方案能够达到。关键在于：如何建立合理的状态转移公式，以及正确处理边界条件。

这种动态规划模式主要用于解决在二维网格（矩阵）中寻找路径或最优解的问题。常见于需要从网格的某个起点出发，按特定规则移动，并在满足约束条件下，求解路径数量或最优代价等问题。

这种模式的典型特点包括：

这类题目多数情况下可以使用二维 DP 数组记录每个位置的状态，也可以在空间优化的情况下转为一维数组或原地修改。

这类题型的关键是明确状态表示、状态转移方程、边界处理，再结合遍历顺序完成递推。

树形 DP 是一种专门用于处理树结构问题的动态规划方法。适用于如下场景：

这种模式常见于解决“在树上如何选择一些节点满足某些条件，使得总收益最大”之类的问题。

这类问题的关键是：定义每个节点的状态表示、状态转移方式、遍历顺序（通常是后序遍历）。

图上的动态规划是一类结合图论算法（如 BFS、Dijkstra、拓扑排序）与动态规划思想来解决最优解问题的方法，适用于如下场景：

这类问题的核心在于：在图的遍历过程中如何用动态规划压缩状态并避免重复计算，同时满足图的结构和约束条件。

这种模式的关键是将大范围数字问题转化为针对每一位数字的状态计算，同时避免暴力枚举每个数字。

位掩码动态规划是一种用于处理状态数量庞大或组合复杂的问题的高效方法，特别适用于那些每种状态都可以用一个整数的二进制位来表示的问题。

这种方法在以下情况下特别有用：

概率型动态规划适用于处理涉及概率计算或期望值计算的问题，特别是在存在随机性或不确定过程的场景下。

这种模式常见于以下几类问题：

这种动态规划方法适用于可以抽象为一系列“状态”以及状态之间的“转移”的问题。通常用于多阶段决策优化场景。

这种模式适用于以下情况：

来源：心平氣和