3.6 动态规划
3.6 动态规划
动态规划（Dynamic Programming），简称 DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。
动态规划三要素：
- 重叠子问题
- 最优子结构
- 状态转移方程
求解动态规划的核心问题是穷举。
但是这类问题的特别之处在于，存在 「重叠子问题」，如果暴力穷举的话效率会极其低下。
动态规划问题一定会具备 「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外问题千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的 「状态转移方程」 才能正确地穷举。
动态规划的解题方法：
- 递归+记忆化（自顶向下）
- 动态规划（自底向上）
动态规划的解题步骤：
- 根据重叠子问题定义状态
- 寻找最优子结构，推导状态转移方程
- 确定 dp 初始状态
- 确定输出值
相关题目
动态规划基础题目
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 509 | 斐波那契数 | [✓] | 递归 记忆化搜索 数学 1+ | |
| 70 | 爬楼梯 | [✓] | 记忆化搜索 数学 动态规划 | |
| 62 | 不同路径 | [✓] | 数学 动态规划 组合数学 |
记忆化搜索
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1137 | 第 N 个泰波那契数 | [✓] | 记忆化搜索 数学 动态规划 | |
| 375 | 猜数字大小 II | [✓] | 数学 动态规划 博弈 | |
| 494 | 目标和 | [✓] | 数组 动态规划 回溯 | |
| 576 | 出界的路径数 | 动态规划 | ||
| 87 | 扰乱字符串 | 字符串 动态规划 | ||
| 403 | 青蛙过河 | 数组 动态规划 | ||
| 552 | 学生出勤记录 II | 动态规划 | ||
| 913 | 猫和老鼠 | 图 拓扑排序 记忆化搜索 3+ | ||
| 329 | 矩阵中的最长递增路径 | 深度优先搜索 广度优先搜索 图 5+ |
线性 DP
- 单串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 300 | 最长递增子序列 | [✓] | 数组 二分查找 动态规划 | |
| 673 | 最长递增子序列的个数 | 树状数组 线段树 数组 1+ | ||
| 354 | 俄罗斯套娃信封问题 | [✓] | 数组 二分查找 动态规划 1+ | |
| 53 | 最大子数组和 | [✓] | 数组 分治 动态规划 | |
| 152 | 乘积最大子数组 | [✓] | 数组 动态规划 | |
| 918 | 环形子数组的最大和 | [✓] | 队列 数组 分治 2+ | |
| 198 | 打家劫舍 | [✓] | 数组 动态规划 | |
| 213 | 打家劫舍 II | 数组 动态规划 | ||
| 740 | 删除并获得点数 | 数组 哈希表 动态规划 | ||
| 1388 | 3n 块披萨 | 贪心 数组 动态规划 1+ | ||
| 873 | 最长的斐波那契子序列的长度 | 数组 哈希表 动态规划 | ||
| 1027 | 最长等差数列 | 数组 哈希表 二分查找 1+ | ||
| 1055 | 形成字符串的最短路径 🔒 | 贪心 双指针 字符串 1+ | ||
| 368 | 最大整除子集 | 数组 数学 动态规划 1+ | ||
| 32 | 最长有效括号 | [✓] | 栈 字符串 动态规划 | |
| 413 | 等差数列划分 | 数组 动态规划 滑动窗口 | ||
| 91 | 解码方法 | 字符串 动态规划 | ||
| 639 | 解码方法 II | 字符串 动态规划 | ||
| 132 | 分割回文串 II | 字符串 动态规划 | ||
| 1220 | 统计元音字母序列的数目 | 动态规划 | ||
| 338 | 比特位计数 | 位运算 动态规划 | ||
| 801 | 使序列递增的最小交换次数 | 数组 动态规划 | ||
| 871 | 最低加油次数 | 贪心 数组 动态规划 1+ | ||
| 45 | 跳跃游戏 II | [✓] | 贪心 数组 动态规划 | |
| 813 | 最大平均值和的分组 | 数组 动态规划 前缀和 | ||
| 887 | 鸡蛋掉落 | 数学 二分查找 动态规划 | ||
| 256 | 粉刷房子 🔒 | 数组 动态规划 | ||
| 265 | 粉刷房子 II 🔒 | 数组 动态规划 | ||
| 1473 | 粉刷房子 III | 数组 动态规划 | ||
| 975 | 奇偶跳 | 栈 数组 动态规划 2+ | ||
| 403 | 青蛙过河 | 数组 动态规划 | ||
| 1478 | 安排邮筒 | 数组 数学 动态规划 1+ | ||
| 1230 | 抛掷硬币 🔒 | 数组 数学 动态规划 1+ | ||
| 410 | 分割数组的最大值 | 贪心 数组 二分查找 2+ | ||
| 1751 | 最多可以参加的会议数目 II | 数组 二分查找 动态规划 1+ | ||
| 1787 | 使所有区间的异或结果为零 | 位运算 数组 动态规划 | ||
| 121 | 买卖股票的最佳时机 | [✓] | 数组 动态规划 | |
| 122 | 买卖股票的最佳时机 II | [✓] | 贪心 数组 动态规划 | |
| 123 | 买卖股票的最佳时机 III | [✓] | 数组 动态规划 | |
| 188 | 买卖股票的最佳时机 IV | [✓] | 数组 动态规划 | |
| 309 | 买卖股票的最佳时机含冷冻期 | [✓] | 数组 动态规划 | |
| 714 | 买卖股票的最佳时机含手续费 | [✓] | 贪心 数组 动态规划 |
- 双串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1143 | 最长公共子序列 | [✓] | 字符串 动态规划 | |
| 712 | 两个字符串的最小ASCII删除和 | [✓] | 字符串 动态规划 | |
| 718 | 最长重复子数组 | 数组 二分查找 动态规划 3+ | ||
| 583 | 两个字符串的删除操作 | [✓] | 字符串 动态规划 | |
| 72 | 编辑距离 | [✓] | 字符串 动态规划 | |
| 44 | 通配符匹配 | [✓] | 贪心 递归 字符串 1+ | |
| 10 | 正则表达式匹配 | [✓] | 递归 字符串 动态规划 | |
| 97 | 交错字符串 | [✓] | 字符串 动态规划 | |
| 115 | 不同的子序列 | 字符串 动态规划 | ||
| 87 | 扰乱字符串 | 字符串 动态规划 |
- 矩阵线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 118 | 杨辉三角 | [✓] | 数组 动态规划 | |
| 119 | 杨辉三角 II | 数组 动态规划 | ||
| 120 | 三角形最小路径和 | [✓] | 数组 动态规划 | |
| 64 | 最小路径和 | [✓] | 数组 动态规划 矩阵 | |
| 174 | 地下城游戏 | [✓] | 数组 动态规划 矩阵 | |
| 221 | 最大正方形 | [✓] | 数组 动态规划 矩阵 | |
| 931 | 下降路径最小和 | [✓] | 数组 动态规划 矩阵 | |
| 576 | 出界的路径数 | 动态规划 | ||
| 85 | 最大矩形 | [✓] | 栈 数组 动态规划 2+ | |
| 363 | 矩形区域不超过 K 的最大数值和 | 数组 二分查找 矩阵 2+ | ||
| 面试题 17.24 | 最大子矩阵 | 数组 动态规划 矩阵 1+ | ||
| 1444 | 切披萨的方案数 | 记忆化搜索 数组 动态规划 1+ |
- 无串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1137 | 第 N 个泰波那契数 | [✓] | 记忆化搜索 数学 动态规划 | |
| 650 | 两个键的键盘 | 数学 动态规划 | ||
| 264 | 丑数 II | [✓] | 哈希表 数学 动态规划 1+ | |
| 279 | 完全平方数 | [✓] | 广度优先搜索 数学 动态规划 | |
| 343 | 整数拆分 | [✓] | 数学 动态规划 |
背包问题
- 0-1 背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 416 | 分割等和子集 | [✓] | 数组 动态规划 | |
| 494 | 目标和 | [✓] | 数组 动态规划 回溯 | |
| 1049 | 最后一块石头的重量 II | [✓] | 数组 动态规划 |
- 完全背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 279 | 完全平方数 | [✓] | 广度优先搜索 数学 动态规划 | |
| 322 | 零钱兑换 | [✓] | 广度优先搜索 数组 动态规划 | |
| 518 | 零钱兑换 II | [✓] | 数组 动态规划 | |
| 139 | 单词拆分 | [✓] | 字典树 记忆化搜索 数组 3+ | |
| 377 | 组合总和 Ⅳ | 数组 动态规划 | ||
| 638 | 大礼包 | 位运算 记忆化搜索 数组 3+ | ||
| 1449 | 数位成本和为目标值的最大数字 | 数组 动态规划 |
多重背包问题
分组背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1155 | 掷骰子等于目标和的方法数 | 动态规划 | ||
| 2585 | 获得分数的方法数 | 数组 动态规划 |
- 多维背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 474 | 一和零 | [✓] | 数组 字符串 动态规划 | |
| 879 | 盈利计划 | 数组 动态规划 | ||
| 1995 | 统计特殊四元组 | 数组 哈希表 枚举 |
区间 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 486 | 预测赢家 | 递归 数组 数学 2+ | ||
| 312 | 戳气球 | 数组 动态规划 | ||
| 877 | 石子游戏 | 数组 数学 动态规划 1+ | ||
| 1000 | 合并石头的最低成本 | 数组 动态规划 前缀和 | ||
| 1547 | 切棍子的最小成本 | 数组 动态规划 排序 | ||
| 664 | 奇怪的打印机 | 字符串 动态规划 | ||
| 1039 | 多边形三角剖分的最低得分 | 数组 动态规划 | ||
| 546 | 移除盒子 | 记忆化搜索 数组 动态规划 | ||
| 375 | 猜数字大小 II | [✓] | 数学 动态规划 博弈 | |
| 678 | 有效的括号字符串 | [✓] | 栈 贪心 字符串 1+ | |
| 5 | 最长回文子串 | [✓] | 双指针 字符串 动态规划 | |
| 516 | 最长回文子序列 | [✓] | 字符串 动态规划 | |
| 730 | 统计不同回文子序列 | 字符串 动态规划 | ||
| 2104 | 子数组范围和 | 栈 数组 单调栈 |
树形 DP
- 固定根的树形 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 543 | 二叉树的直径 | [✓] | 树 深度优先搜索 二叉树 | |
| 124 | 二叉树中的最大路径和 | [✓] | 树 深度优先搜索 动态规划 1+ | |
| 1245 | 树的直径 🔒 | 树 深度优先搜索 广度优先搜索 2+ | ||
| 2246 | 相邻字符不同的最长路径 | 树 深度优先搜索 图 3+ | ||
| 687 | 最长同值路径 | 树 深度优先搜索 二叉树 | ||
| 337 | 打家劫舍 III | 树 深度优先搜索 动态规划 1+ | ||
| 333 | 最大二叉搜索子树 🔒 | 树 深度优先搜索 二叉搜索树 2+ | ||
| 1617 | 统计子树中城市之间最大距离 | 位运算 树 动态规划 2+ | ||
| 2538 | 最大价值和与最小价值和的差值 | 树 深度优先搜索 数组 1+ | ||
| 1569 | 将子数组重新排序得到同一个二叉搜索树的方案数 | 树 并查集 二叉搜索树 7+ | ||
| 1372 | 二叉树中的最长交错路径 | 树 深度优先搜索 动态规划 1+ | ||
| 1373 | 二叉搜索子树的最大键值和 | 树 深度优先搜索 二叉搜索树 2+ | ||
| 968 | 监控二叉树 | 树 深度优先搜索 动态规划 1+ | ||
| 1273 | 删除树节点 🔒 | 树 深度优先搜索 广度优先搜索 1+ | ||
| 1519 | 子树中标签相同的节点数 | 树 深度优先搜索 广度优先搜索 2+ |
- 不定根的树形 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 310 | 最小高度树 | 深度优先搜索 广度优先搜索 图 1+ | ||
| 834 | 树中距离之和 | 树 深度优先搜索 图 1+ | ||
| 2581 | 统计可能的树根数目 | 树 深度优先搜索 数组 2+ |
状态压缩 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1879 | 两个数组最小的异或值之和 | 位运算 数组 动态规划 1+ | ||
| 2172 | 数组的最大与和 | 位运算 数组 动态规划 1+ | ||
| 1947 | 最大兼容性评分和 | 位运算 数组 动态规划 2+ | ||
| 1595 | 连通两组点的最小成本 | 位运算 数组 动态规划 2+ | ||
| 1494 | 并行课程 II | 位运算 图 动态规划 1+ | ||
| 1655 | 分配重复整数 | 位运算 数组 动态规划 2+ | ||
| 1986 | 完成任务的最少工作时间段 | 位运算 数组 动态规划 2+ | ||
| 1434 | 每个人戴不同帽子的方案数 | 位运算 数组 动态规划 1+ | ||
| 1799 | N 次操作后的最大分数和 | 位运算 数组 数学 4+ | ||
| 1681 | 最小不兼容性 | 位运算 数组 动态规划 1+ | ||
| 526 | 优美的排列 | 位运算 数组 动态规划 2+ | ||
| 351 | 安卓系统手势解锁 🔒 | 位运算 动态规划 回溯 1+ | ||
| 464 | 我能赢吗 | 位运算 记忆化搜索 数学 3+ | ||
| 847 | 访问所有节点的最短路径 | 位运算 广度优先搜索 图 2+ | ||
| 638 | 大礼包 | 位运算 记忆化搜索 数组 3+ | ||
| 1994 | 好子集的数目 | 位运算 数组 数学 2+ | ||
| 1349 | 参加考试的最大学生数 | 位运算 数组 动态规划 2+ | ||
| 698 | 划分为k个相等的子集 | 位运算 记忆化搜索 数组 3+ | ||
| 943 | 最短超级串 | 位运算 数组 字符串 2+ | ||
| 691 | 贴纸拼词 | 位运算 数组 字符串 3+ | ||
| 982 | 按位与为零的三元组 | 位运算 数组 哈希表 |
计数 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 62 | 不同路径 | [✓] | 数学 动态规划 组合数学 | |
| 63 | 不同路径 II | [✓] | 数组 动态规划 矩阵 | |
| 343 | 整数拆分 | [✓] | 数学 动态规划 | |
| 96 | 不同的二叉搜索树 | [✓] | 树 二叉搜索树 数学 2+ | |
| 1259 | 不相交的握手 🔒 | 数学 动态规划 | ||
| 790 | 多米诺和托米诺平铺 | 动态规划 | ||
| 70 | 爬楼梯 | [✓] | 记忆化搜索 数学 动态规划 | |
| 746 | 使用最小花费爬楼梯 | 数组 动态规划 | ||
| 509 | 斐波那契数 | [✓] | 递归 记忆化搜索 数学 1+ | |
| 1137 | 第 N 个泰波那契数 | [✓] | 记忆化搜索 数学 动态规划 |
数位 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 2376 | 统计特殊整数 | 数学 动态规划 | ||
| 357 | 统计各位数字都不同的数字个数 | 数学 动态规划 回溯 | ||
| 1012 | 至少有 1 位重复的数字 | 数学 动态规划 | ||
| 902 | 最大为 N 的数字组合 | 数组 数学 字符串 2+ | ||
| 788 | 旋转数字 | 数学 动态规划 | ||
| 600 | 不含连续1的非负整数 | 动态规划 | ||
| 233 | 数字 1 的个数 | [✓] | 递归 数学 动态规划 | |
| 2719 | 统计整数数目 | 数学 字符串 动态规划 | ||
| 248 | 中心对称数 III 🔒 | 递归 数组 字符串 | ||
| 1088 | 易混淆数 II 🔒 | 数学 回溯 | ||
| 1067 | 范围内的数字计数 🔒 | 数学 动态规划 | ||
| 1742 | 盒子中小球的最大数量 | 哈希表 数学 计数 | ||
| 面试题 17.06 | 2出现的次数 | 递归 数学 动态规划 |
概率 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 688 | 骑士在棋盘上的概率 | 动态规划 | ||
| 808 | 分汤 | 数学 动态规划 概率与统计 | ||
| 837 | 新 21 点 | 数学 动态规划 滑动窗口 1+ | ||
| 1230 | 抛掷硬币 🔒 | 数组 数学 动态规划 1+ | ||
| 1467 | 两个盒子中球的颜色数相同的概率 | 数组 数学 动态规划 3+ | ||
| 1227 | 飞机座位分配概率 | 脑筋急转弯 数学 动态规划 1+ | ||
| 1377 | T 秒后青蛙的位置 | 树 深度优先搜索 广度优先搜索 1+ | ||
| 剑指 Offer 60 | n个骰子的点数 | [✓] | 数学 动态规划 概率与统计 |