跳至主要內容

3.6 动态规划

3.6 动态规划

动态规划（Dynamic Programming），简称 DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。

动态规划三要素：

  • 重叠子问题
  • 最优子结构
  • 状态转移方程

求解动态规划的核心问题是穷举。

但是这类问题的特别之处在于，存在 「重叠子问题」，如果暴力穷举的话效率会极其低下。

动态规划问题一定会具备 「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外问题千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的 「状态转移方程」 才能正确地穷举。

动态规划的解题方法：

  • 递归+记忆化（自顶向下）
  • 动态规划（自底向上）

动态规划的解题步骤：

  • 根据重叠子问题定义状态
  • 寻找最优子结构，推导状态转移方程
  • 确定 dp 初始状态
  • 确定输出值

相关题目

动态规划基础题目

题号标题题解标签难度力扣
509斐波那契数[✓]递归 记忆化搜索 数学 1+🟢🀄️open in new window 🔗open in new window
70爬楼梯[✓]记忆化搜索 数学 动态规划🟢🀄️open in new window 🔗open in new window
62不同路径[✓]数学 动态规划 组合数学🟠🀄️open in new window 🔗open in new window

记忆化搜索

题号标题题解标签难度力扣
1137第 N 个泰波那契数[✓]记忆化搜索 数学 动态规划🟢🀄️open in new window 🔗open in new window
375猜数字大小 II[✓]数学 动态规划 博弈🟠🀄️open in new window 🔗open in new window
494目标和[✓]数组 动态规划 回溯🟠🀄️open in new window 🔗open in new window
576出界的路径数动态规划🟠🀄️open in new window 🔗open in new window
87扰乱字符串字符串 动态规划🔴🀄️open in new window 🔗open in new window
403青蛙过河数组 动态规划🔴🀄️open in new window 🔗open in new window
552学生出勤记录 II动态规划🔴🀄️open in new window 🔗open in new window
913猫和老鼠图 拓扑排序 记忆化搜索 3+🔴🀄️open in new window 🔗open in new window
329矩阵中的最长递增路径[✓]深度优先搜索 广度优先搜索 图 5+🔴🀄️open in new window 🔗open in new window

线性 DP

  • 单串线性 DP 问题
题号标题题解标签难度力扣
300最长递增子序列[✓]数组 二分查找 动态规划🟠🀄️open in new window 🔗open in new window
673最长递增子序列的个数[✓]树状数组 线段树 数组 1+🟠🀄️open in new window 🔗open in new window
354俄罗斯套娃信封问题[✓]数组 二分查找 动态规划 1+🔴🀄️open in new window 🔗open in new window
53最大子数组和[✓]数组 分治 动态规划🟠🀄️open in new window 🔗open in new window
152乘积最大子数组[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
918环形子数组的最大和[✓]队列 数组 分治 2+🟠🀄️open in new window 🔗open in new window
198打家劫舍[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
213打家劫舍 II[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
740删除并获得点数[✓]数组 哈希表 动态规划🟠🀄️open in new window 🔗open in new window
13883n 块披萨贪心 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
873最长的斐波那契子序列的长度[✓]数组 哈希表 动态规划🟠🀄️open in new window 🔗open in new window
1027最长等差数列[✓]数组 哈希表 二分查找 1+🟠🀄️open in new window 🔗open in new window
1055形成字符串的最短路径 🔒贪心 双指针 字符串 1+🟠🀄️open in new window 🔗open in new window
368最大整除子集[✓]数组 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window
32最长有效括号[✓]栈 字符串 动态规划🔴🀄️open in new window 🔗open in new window
413等差数列划分[✓]数组 动态规划 滑动窗口🟠🀄️open in new window 🔗open in new window
91解码方法[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
639解码方法 II字符串 动态规划🔴🀄️open in new window 🔗open in new window
132分割回文串 II[✓]字符串 动态规划🔴🀄️open in new window 🔗open in new window
1220统计元音字母序列的数目动态规划🔴🀄️open in new window 🔗open in new window
338比特位计数[✓]位运算 动态规划🟢🀄️open in new window 🔗open in new window
801使序列递增的最小交换次数数组 动态规划🔴🀄️open in new window 🔗open in new window
871最低加油次数贪心 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
45跳跃游戏 II[✓]贪心 数组 动态规划🟠🀄️open in new window 🔗open in new window
813最大平均值和的分组数组 动态规划 前缀和🟠🀄️open in new window 🔗open in new window
887鸡蛋掉落数学 二分查找 动态规划🔴🀄️open in new window 🔗open in new window
256粉刷房子 🔒数组 动态规划🟠🀄️open in new window 🔗open in new window
265粉刷房子 II 🔒数组 动态规划🔴🀄️open in new window 🔗open in new window
1473粉刷房子 III数组 动态规划🔴🀄️open in new window 🔗open in new window
975奇偶跳栈 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
403青蛙过河数组 动态规划🔴🀄️open in new window 🔗open in new window
1478安排邮筒数组 数学 动态规划 1+🔴🀄️open in new window 🔗open in new window
1230抛掷硬币 🔒数组 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window
410分割数组的最大值贪心 数组 二分查找 2+🔴🀄️open in new window 🔗open in new window
1751最多可以参加的会议数目 II数组 二分查找 动态规划 1+🔴🀄️open in new window 🔗open in new window
1787使所有区间的异或结果为零位运算 数组 动态规划🔴🀄️open in new window 🔗open in new window
121买卖股票的最佳时机[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
122买卖股票的最佳时机 II[✓]贪心 数组 动态规划🟠🀄️open in new window 🔗open in new window
123买卖股票的最佳时机 III[✓]数组 动态规划🔴🀄️open in new window 🔗open in new window
188买卖股票的最佳时机 IV[✓]数组 动态规划🔴🀄️open in new window 🔗open in new window
309买卖股票的最佳时机含冷冻期[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
714买卖股票的最佳时机含手续费[✓]贪心 数组 动态规划🟠🀄️open in new window 🔗open in new window
  • 双串线性 DP 问题
题号标题题解标签难度力扣
1143最长公共子序列[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
712两个字符串的最小ASCII删除和[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
718最长重复子数组数组 二分查找 动态规划 3+🟠🀄️open in new window 🔗open in new window
583两个字符串的删除操作[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
72编辑距离[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
44通配符匹配[✓]贪心 递归 字符串 1+🔴🀄️open in new window 🔗open in new window
10正则表达式匹配[✓]递归 字符串 动态规划🔴🀄️open in new window 🔗open in new window
97交错字符串[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
115不同的子序列[✓]字符串 动态规划🔴🀄️open in new window 🔗open in new window
87扰乱字符串字符串 动态规划🔴🀄️open in new window 🔗open in new window
  • 矩阵线性 DP 问题
题号标题题解标签难度力扣
118杨辉三角[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
119杨辉三角 II[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
120三角形最小路径和[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
64最小路径和[✓]数组 动态规划 矩阵🟠🀄️open in new window 🔗open in new window
174地下城游戏[✓]数组 动态规划 矩阵🔴🀄️open in new window 🔗open in new window
221最大正方形[✓]数组 动态规划 矩阵🟠🀄️open in new window 🔗open in new window
931下降路径最小和[✓]数组 动态规划 矩阵🟠🀄️open in new window 🔗open in new window
576出界的路径数动态规划🟠🀄️open in new window 🔗open in new window
85最大矩形[✓]栈 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
363矩形区域不超过 K 的最大数值和数组 二分查找 矩阵 2+🔴🀄️open in new window 🔗open in new window
面试题 17.24最大子矩阵数组 动态规划 矩阵 1+🔴🀄️open in new window
1444切披萨的方案数记忆化搜索 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
  • 无串线性 DP 问题
题号标题题解标签难度力扣
1137第 N 个泰波那契数[✓]记忆化搜索 数学 动态规划🟢🀄️open in new window 🔗open in new window
650两个键的键盘数学 动态规划🟠🀄️open in new window 🔗open in new window
264丑数 II[✓]哈希表 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window
279完全平方数[✓]广度优先搜索 数学 动态规划🟠🀄️open in new window 🔗open in new window
343整数拆分[✓]数学 动态规划🟠🀄️open in new window 🔗open in new window

背包问题

  • 0-1 背包问题
题号标题题解标签难度力扣
416分割等和子集[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
494目标和[✓]数组 动态规划 回溯🟠🀄️open in new window 🔗open in new window
1049最后一块石头的重量 II[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
  • 完全背包问题
题号标题题解标签难度力扣
279完全平方数[✓]广度优先搜索 数学 动态规划🟠🀄️open in new window 🔗open in new window
322零钱兑换[✓]广度优先搜索 数组 动态规划🟠🀄️open in new window 🔗open in new window
518零钱兑换 II[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
139单词拆分[✓]字典树 记忆化搜索 数组 3+🟠🀄️open in new window 🔗open in new window
377组合总和 Ⅳ[✓]数组 动态规划🟠🀄️open in new window 🔗open in new window
638大礼包[✓]位运算 记忆化搜索 数组 3+🟠🀄️open in new window 🔗open in new window
1449数位成本和为目标值的最大数字数组 动态规划🔴🀄️open in new window 🔗open in new window

  • 多重背包问题

  • 分组背包问题

题号标题题解标签难度力扣
1155掷骰子等于目标和的方法数动态规划🟠🀄️open in new window 🔗open in new window
2585获得分数的方法数数组 动态规划🔴🀄️open in new window 🔗open in new window
  • 多维背包问题
题号标题题解标签难度力扣
474一和零[✓]数组 字符串 动态规划🟠🀄️open in new window 🔗open in new window
879盈利计划数组 动态规划🔴🀄️open in new window 🔗open in new window
1995统计特殊四元组[✓]数组 哈希表 枚举🟢🀄️open in new window 🔗open in new window

区间 DP

题号标题题解标签难度力扣
486预测赢家[✓]递归 数组 数学 2+🟠🀄️open in new window 🔗open in new window
312戳气球数组 动态规划🔴🀄️open in new window 🔗open in new window
877石子游戏数组 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window
1000合并石头的最低成本数组 动态规划 前缀和🔴🀄️open in new window 🔗open in new window
1547切棍子的最小成本数组 动态规划 排序🔴🀄️open in new window 🔗open in new window
664奇怪的打印机字符串 动态规划🔴🀄️open in new window 🔗open in new window
1039多边形三角剖分的最低得分数组 动态规划🟠🀄️open in new window 🔗open in new window
546移除盒子记忆化搜索 数组 动态规划🔴🀄️open in new window 🔗open in new window
375猜数字大小 II[✓]数学 动态规划 博弈🟠🀄️open in new window 🔗open in new window
678有效的括号字符串[✓]栈 贪心 字符串 1+🟠🀄️open in new window 🔗open in new window
5最长回文子串[✓]双指针 字符串 动态规划🟠🀄️open in new window 🔗open in new window
516最长回文子序列[✓]字符串 动态规划🟠🀄️open in new window 🔗open in new window
730统计不同回文子序列字符串 动态规划🔴🀄️open in new window 🔗open in new window
2104子数组范围和栈 数组 单调栈🟠🀄️open in new window 🔗open in new window

树形 DP

  • 固定根的树形 DP
题号标题题解标签难度力扣
543二叉树的直径[✓]树 深度优先搜索 二叉树🟢🀄️open in new window 🔗open in new window
124二叉树中的最大路径和[✓]树 深度优先搜索 动态规划 1+🔴🀄️open in new window 🔗open in new window
1245树的直径 🔒树 深度优先搜索 广度优先搜索 2+🟠🀄️open in new window 🔗open in new window
2246相邻字符不同的最长路径树 深度优先搜索 图 3+🔴🀄️open in new window 🔗open in new window
687最长同值路径树 深度优先搜索 二叉树🟠🀄️open in new window 🔗open in new window
337打家劫舍 III[✓]树 深度优先搜索 动态规划 1+🟠🀄️open in new window 🔗open in new window
333最大二叉搜索子树 🔒树 深度优先搜索 二叉搜索树 2+🟠🀄️open in new window 🔗open in new window
1617统计子树中城市之间最大距离位运算 树 动态规划 2+🔴🀄️open in new window 🔗open in new window
2538最大价值和与最小价值和的差值树 深度优先搜索 数组 1+🔴🀄️open in new window 🔗open in new window
1569将子数组重新排序得到同一个二叉搜索树的方案数树 并查集 二叉搜索树 7+🔴🀄️open in new window 🔗open in new window
1372二叉树中的最长交错路径[✓]树 深度优先搜索 动态规划 1+🟠🀄️open in new window 🔗open in new window
1373二叉搜索子树的最大键值和树 深度优先搜索 二叉搜索树 2+🔴🀄️open in new window 🔗open in new window
968监控二叉树树 深度优先搜索 动态规划 1+🔴🀄️open in new window 🔗open in new window
1273删除树节点 🔒树 深度优先搜索 广度优先搜索 1+🟠🀄️open in new window 🔗open in new window
1519子树中标签相同的节点数树 深度优先搜索 广度优先搜索 2+🟠🀄️open in new window 🔗open in new window
  • 不定根的树形 DP
题号标题题解标签难度力扣
310最小高度树[✓]深度优先搜索 广度优先搜索 图 1+🟠🀄️open in new window 🔗open in new window
834树中距离之和树 深度优先搜索 图 1+🔴🀄️open in new window 🔗open in new window
2581统计可能的树根数目树 深度优先搜索 数组 2+🔴🀄️open in new window 🔗open in new window

状态压缩 DP

题号标题题解标签难度力扣
1879两个数组最小的异或值之和位运算 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
2172数组的最大与和位运算 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
1947最大兼容性评分和位运算 数组 动态规划 2+🟠🀄️open in new window 🔗open in new window
1595连通两组点的最小成本位运算 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
1494并行课程 II位运算 图 动态规划 1+🔴🀄️open in new window 🔗open in new window
1655分配重复整数位运算 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
1986完成任务的最少工作时间段位运算 数组 动态规划 2+🟠🀄️open in new window 🔗open in new window
1434每个人戴不同帽子的方案数位运算 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
1799N 次操作后的最大分数和位运算 数组 数学 4+🔴🀄️open in new window 🔗open in new window
1681最小不兼容性位运算 数组 动态规划 1+🔴🀄️open in new window 🔗open in new window
526优美的排列[✓]位运算 数组 动态规划 2+🟠🀄️open in new window 🔗open in new window
351安卓系统手势解锁 🔒位运算 动态规划 回溯 1+🟠🀄️open in new window 🔗open in new window
464我能赢吗[✓]位运算 记忆化搜索 数学 3+🟠🀄️open in new window 🔗open in new window
847访问所有节点的最短路径位运算 广度优先搜索 图 2+🔴🀄️open in new window 🔗open in new window
638大礼包[✓]位运算 记忆化搜索 数组 3+🟠🀄️open in new window 🔗open in new window
1994好子集的数目位运算 数组 数学 2+🔴🀄️open in new window 🔗open in new window
1349参加考试的最大学生数位运算 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
698划分为k个相等的子集位运算 记忆化搜索 数组 3+🟠🀄️open in new window 🔗open in new window
943最短超级串位运算 数组 字符串 2+🔴🀄️open in new window 🔗open in new window
691贴纸拼词位运算 数组 字符串 3+🔴🀄️open in new window 🔗open in new window
982按位与为零的三元组位运算 数组 哈希表🔴🀄️open in new window 🔗open in new window

计数 DP

题号标题题解标签难度力扣
62不同路径[✓]数学 动态规划 组合数学🟠🀄️open in new window 🔗open in new window
63不同路径 II[✓]数组 动态规划 矩阵🟠🀄️open in new window 🔗open in new window
343整数拆分[✓]数学 动态规划🟠🀄️open in new window 🔗open in new window
96不同的二叉搜索树[✓]树 二叉搜索树 数学 2+🟠🀄️open in new window 🔗open in new window
1259不相交的握手 🔒数学 动态规划🔴🀄️open in new window 🔗open in new window
790多米诺和托米诺平铺[✓]动态规划🟠🀄️open in new window 🔗open in new window
70爬楼梯[✓]记忆化搜索 数学 动态规划🟢🀄️open in new window 🔗open in new window
746使用最小花费爬楼梯[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
509斐波那契数[✓]递归 记忆化搜索 数学 1+🟢🀄️open in new window 🔗open in new window
1137第 N 个泰波那契数[✓]记忆化搜索 数学 动态规划🟢🀄️open in new window 🔗open in new window

数位 DP

题号标题题解标签难度力扣
2376统计特殊整数数学 动态规划🔴🀄️open in new window 🔗open in new window
357统计各位数字都不同的数字个数[✓]数学 动态规划 回溯🟠🀄️open in new window 🔗open in new window
1012至少有 1 位重复的数字数学 动态规划🔴🀄️open in new window 🔗open in new window
902最大为 N 的数字组合数组 数学 字符串 2+🔴🀄️open in new window 🔗open in new window
788旋转数字数学 动态规划🟠🀄️open in new window 🔗open in new window
600不含连续1的非负整数动态规划🔴🀄️open in new window 🔗open in new window
233数字 1 的个数[✓]递归 数学 动态规划🔴🀄️open in new window 🔗open in new window
2719统计整数数目数学 字符串 动态规划🔴🀄️open in new window 🔗open in new window
248中心对称数 III 🔒递归 数组 字符串🔴🀄️open in new window 🔗open in new window
1088易混淆数 II 🔒数学 回溯🔴🀄️open in new window 🔗open in new window
1067范围内的数字计数 🔒数学 动态规划🔴🀄️open in new window 🔗open in new window
1742盒子中小球的最大数量[✓]哈希表 数学 计数🟢🀄️open in new window 🔗open in new window
面试题 17.062出现的次数递归 数学 动态规划🔴🀄️open in new window

概率 DP

题号标题题解标签难度力扣
688骑士在棋盘上的概率动态规划🟠🀄️open in new window 🔗open in new window
808分汤数学 动态规划 概率与统计🟠🀄️open in new window 🔗open in new window
837新 21 点数学 动态规划 滑动窗口 1+🟠🀄️open in new window 🔗open in new window
1230抛掷硬币 🔒数组 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window
1467两个盒子中球的颜色数相同的概率数组 数学 动态规划 3+🔴🀄️open in new window 🔗open in new window
1227飞机座位分配概率脑筋急转弯 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window
1377T 秒后青蛙的位置树 深度优先搜索 广度优先搜索 1+🔴🀄️open in new window 🔗open in new window
剑指 Offer 60n个骰子的点数[✓]数学 动态规划 概率与统计🟠🀄️open in new window