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

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

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

斐波那契数列模式

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

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

F(n) = F(n-1) + F(n-2)，

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

LeetCode 题目

• LeetCode 70：爬楼梯
• LeetCode 509：斐波那契数
• LeetCode 746：使用最小花费爬楼梯

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

Kadane算法

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

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

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

LeetCode 题目

• LeetCode 53：最大子数组和
• LeetCode 918：环形子数组的最大和
• LeetCode 152：乘积最大子数组

0/1 背包问题模式

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

• 给定一组物品，每个物品都有一个重量和一个价值（或分数）；
• 需要从中选择若干物品组成一个子集；
• 总重量（或某种资源）受到限制；
• 目标是使所选物品的总价值最大化（或最小化）；
• 每个物品只能选择一次（“0/1” 的含义：要么选，要么不选）。

LeetCode 题目

• LeetCode 416：分割等和子集
• LeetCode 494：目标和
• LeetCode 1049：最后一块石头的重量 II

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

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

完全背包问题模式

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

• 给定一组物品，每个物品有一个重量和一个价值；
• 你需要选择一些物品，使得总价值最大（或最小）；
• 总重量（或其他资源）受到限制；
• 和 0/1 背包不同的是：每种物品可以选取多次，数量不限，可以理解为物品的供应是无限的。

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

LeetCode 题目

• LeetCode 322：零钱兑换
• LeetCode 518：零钱兑换 II
• LeetCode 279：完全平方数

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

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

最长公共子序列模式（LCS）

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

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

LeetCode 题目

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

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

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

最长递增子序列模式（LIS）

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

• 子序列不要求连续，但元素的相对顺序不能改变；
• LIS 常被应用于排序、嵌套结构、动态过程中的最优子结构等场景；

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

LeetCode 题目

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

最长递增子序列模式是序列型动态规划的核心之一，理解它有助于解决大量“选取最优子序列”相关的问题。

回文子序列模式（Palindromic Subsequence）

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

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

• 找出最长的回文子序列或子串，
• 或者通过最少的操作（如插入、删除）将字符串变为回文。

LeetCode 题目

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

编辑距离模式（Edit Distance）

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

• 插入一个字符（Insert）
• 删除一个字符（Delete）
• 替换一个字符（Substitute）

LeetCode 题目

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

子集和模式（Subset Sum）

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

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

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

LeetCode 题目

• LeetCode 416：分割等和子集
• LeetCode 494：目标和
• LeetCode 698：划分为k个相等子集

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

字符串切分模式

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

这类问题的特点包括：

• 题目本身是关于字符串或序列的；
• 需要将字符串按照某种规则拆分成多个子串或子序列；
• 要在所有可能的切分方式中，找出最优解（比如代价最小、次数最少等）；
• 整体问题的解可以通过若干个子串上的子问题组合而成；
• 不同的切分方式会影响结果，需要枚举或动态规划来选择最佳切分点。

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

LeetCode 题目

• LeetCode 132：最少回文切分
• LeetCode 131：所有回文切分
• LeetCode 139：单词拆分

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

卡特兰数模式（Catalan Numbers）

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

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

• 括号匹配：给定括号对数，计算可以生成多少种合法的括号组合；
• 二叉搜索树（BST）：给定节点个数，计算可以构成多少种不同的二叉搜索树；
• 一个 n+2 边的多边形，有多少种不同的方式将其划分为多个三角形（多边形三角剖分）。

LeetCode 题目

• LeetCode 96：唯一的二叉搜索树
• LeetCode 22：括号生成

矩阵链乘法

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

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

• 面对的是一组可以两两组合的元素序列；
• 组合的代价取决于组合的顺序；
• 需要找到一种最优的组合方式：在所有可能的顺序中，使总成本最小

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

LeetCode 题目

• LeetCode 1039：多边形三角剖分的最低得分
• LeetCode 312：戳气球
• LeetCode 1000：合并石头的最低成本

计数问题（Count Distinct Ways）

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

• 需要统计达成某个目标或状态所有可能的方案数；
• 问题通常涉及一系列选择或步骤，通过不同路径达到目标；
• 存在多种有效路径或组合方式，都能得出正确答案；
• 整个问题可以拆解成多个子问题，而且子问题之间会有重叠；
• 本质上是组合型动态规划，题目一般会问：“有多少种方式可以做到……？

LeetCode 题目

• LeetCode 91：解码方法
• LeetCode 2266：统计可以输入的文本消息数

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

网格型动态规划（DP on Grids）

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

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

• 题目背景是一个二维数组（矩阵），每个格子表示一种状态或代价；
• 常见的移动方向包括向右、向下、或对角线方向；
• 当前格子的最优解，依赖于其相邻格子的结果；

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

LeetCode 题目

• LeetCode 62：不同路径
• LeetCode 64：最小路径和
• LeetCode 329：矩阵中的最长递增路径

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

树形动态规划（DP on Trees）

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

• 问题的数据结构是树（由节点和边组成，具有层级和父子关系）；
• 问题可以分解为以子树为单位的子问题，然后通过合并子问题的结果来构建整棵树的解；
• 需要在每个节点上做决策，这些决策会对它的子节点或父节点产生影响；
• 通常需要从底向上（后序遍历）来计算每个节点的值，而每个节点的最终解依赖于其子树的结果。

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

LeetCode 题目

• LeetCode 337：打家劫舍 III
• LeetCode 124：二叉树中的最大路径和
• LeetCode 968：监控二叉树

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

图上的动态规划（DP on Graphs）

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

• 问题的数据结构是图（可能是有向或无向图）；
• 通常需要在图中寻找某种最优路径，例如最短路径、最长路径、带约束的路径、最小花费路径等；
• 节点的状态依赖于相邻节点或者所在的连通分量；
• 在遍历图的过程中，需要记录并维护某些状态信息，比如走了多少步、花了多少钱等，以确保满足题目的约束条件。

LeetCode 题目

• LeetCode 787：K 站以内最便宜的航班
• LeetCode 1334：到其他城市最少的城市

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

数字动态规划（Digit DP）

数字动态规划模式非常适合用于解决以下类型的问题：

• 需要对某个范围内的数字进行计数或求和的问题；
• 问题与数字的每一位相关，而不能只看整体；
• 数字范围非常大（通常达到 10^18或更大），因此暴力破解的方法不可行；
• 问题涉及到数字的特定数位限制。

LeetCode 题目

• LeetCode 357：计算没有重复数字的数字个数
• LeetCode 233：数字 1 出现的次数
• LeetCode 902：给定数字集合，找出小于等于 N 的数字个数

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

位掩码动态规划（Bitmasking DP）

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

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

• 问题涉及子集或元素组合，比如从一组元素中选取若干个的各种方案；
• 元素总数相对较少（一般不超过 20～30 个），否则状态空间会过大；
• 需要高效表示和操作元素集合（如某个元素是否被选中或访问）；
• 问题中需要对每个元素做“选/不选”或“访问/未访问”的决策；
• 想要在动态规划中优化空间使用，通过整数的位来记录状态比数组节省很多内存。

LeetCode 题目

• LeetCode 1986：完成任务所需要的最少工作次数
• LeetCode 2305：Cookie 的公平分配
• LeetCode 847：访问所有节点的最短路径

概率型动态规划（Probability DP）

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

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

• 问题本身涉及概率过程，比如棋盘上的随机移动、投骰子、抽牌等；
• 一个状态的概率取决于先前状态的概率；
• 目标是计算某种结果出现的概率，或者求一个随机过程的期望值；
• 通常会设计一个 dp[i][j] 表示在状态 (i,j) 下的概率或期望值（例如：dp[i] 表示第 i 步时的期望得分）；
• 穷举全部可能性不可行，需要通过状态转移公式来递推。

LeetCode 题目

• LeetCode 688：骑士在棋盘上的概率
• LeetCode 808：汤匙盛汤问题
• LeetCode 837. 新的 21 点游戏

状态机型动态规划（State Machine DP）

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

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

• 该问题可以建模为一系列状态以及这些状态之间的转换；
• 存在明确的状态转移规则，每次操作都会使当前状态向某个其他状态转移；
• 最终的最优解取决于一系列合理的状态转移路径；
• 在求解过程中，往往需要做出选择，这些选择会影响未来的状态和收益；
• 状态的数量是有限且可枚举的，每个状态都可以明确定义（例如：是否持有股票、是否处于冷却期等）。

LeetCode 题目

• LeetCode 309：买卖股票的最佳时机
• LeetCode 123：买卖股票的最佳时机 III