3.6 动态规划
3.6 动态规划
动态规划（Dynamic Programming），简称 DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。
动态规划三要素：
- 重叠子问题
- 最优子结构
- 状态转移方程
求解动态规划的核心问题是穷举。
但是这类问题的特别之处在于，存在 「重叠子问题」，如果暴力穷举的话效率会极其低下。
动态规划问题一定会具备 「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外问题千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的 「状态转移方程」 才能正确地穷举。
动态规划的解题方法：
- 递归+记忆化（自顶向下）
- 动态规划（自底向上）
动态规划的解题步骤：
- 根据重叠子问题定义状态
- 寻找最优子结构，推导状态转移方程
- 确定dp初始状态
- 确定输出值
相关题目
动态规划基础题目
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0509 | 斐波那契数 | JS | 递归 记忆化搜索 数学 1+ | |
| 0070 | 爬楼梯 | JS | 记忆化搜索 数学 动态规划 | |
| 0062 | 不同路径 | JS | 数学 动态规划 组合数学 |
记忆化搜索
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1137 | 第 N 个泰波那契数 | JS | 记忆化搜索 数学 动态规划 | |
| 0375 | 猜数字大小 II | JS | 数学 动态规划 博弈 | |
| 0494 | 目标和 | JS | 数组 动态规划 回溯 | |
| 0576 | 出界的路径数 | 动态规划 | ||
| 0087 | 扰乱字符串 | 字符串 动态规划 | ||
| 0403 | 青蛙过河 | 数组 动态规划 | ||
| 0552 | 学生出勤记录 II | 动态规划 | ||
| 0913 | 猫和老鼠 | 图 拓扑排序 记忆化搜索 3+ | ||
| 0329 | 矩阵中的最长递增路径 | 深度优先搜索 广度优先搜索 图 5+ |
线性 DP
- 单串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0300 | 最长递增子序列 | JS | 数组 二分查找 动态规划 | |
| 0673 | 最长递增子序列的个数 | 树状数组 线段树 数组 1+ | ||
| 0354 | 俄罗斯套娃信封问题 | JS | 数组 二分查找 动态规划 1+ | |
| 0053 | 最大子数组和 | JS | 数组 分治 动态规划 | |
| 0152 | 乘积最大子数组 | JS | 数组 动态规划 | |
| 0918 | 环形子数组的最大和 | 队列 数组 分治 2+ | ||
| 0198 | 打家劫舍 | JS | 数组 动态规划 | |
| 0213 | 打家劫舍 II | 数组 动态规划 | ||
| 0740 | 删除并获得点数 | 数组 哈希表 动态规划 | ||
| 1388 | 3n 块披萨 | 贪心 数组 动态规划 1+ | ||
| 0873 | 最长的斐波那契子序列的长度 | 数组 哈希表 动态规划 | ||
| 1027 | 最长等差数列 | 数组 哈希表 二分查找 1+ | ||
| 1055 | 形成字符串的最短路径 | 贪心 双指针 字符串 | ||
| 0368 | 最大整除子集 | 数组 数学 动态规划 1+ | ||
| 0032 | 最长有效括号 | 栈 字符串 动态规划 | ||
| 0413 | 等差数列划分 | 数组 动态规划 | ||
| 0091 | 解码方法 | 字符串 动态规划 | ||
| 0639 | 解码方法 II | 字符串 动态规划 | ||
| 0132 | 分割回文串 II | 字符串 动态规划 | ||
| 1220 | 统计元音字母序列的数目 | 动态规划 | ||
| 0338 | 比特位计数 | 位运算 动态规划 | ||
| 0801 | 使序列递增的最小交换次数 | 数组 动态规划 | ||
| 0871 | 最低加油次数 | 贪心 数组 动态规划 1+ | ||
| 0045 | 跳跃游戏 II | 贪心 数组 动态规划 | ||
| 0813 | 最大平均值和的分组 | 数组 动态规划 前缀和 | ||
| 0887 | 鸡蛋掉落 | 数学 二分查找 动态规划 | ||
| 0256 | 粉刷房子 | 数组 动态规划 | ||
| 0265 | 粉刷房子 II | 数组 动态规划 | ||
| 1473 | 粉刷房子 III | 数组 动态规划 | ||
| 0975 | 奇偶跳 | 栈 数组 动态规划 2+ | ||
| 0403 | 青蛙过河 | 数组 动态规划 | ||
| 1478 | 安排邮筒 | 数组 数学 动态规划 1+ | ||
| 1230 | 抛掷硬币 | 数学 动态规划 概率与统计 | ||
| 0410 | 分割数组的最大值 | 贪心 数组 二分查找 2+ | ||
| 1751 | 最多可以参加的会议数目 II | 数组 二分查找 动态规划 1+ | ||
| 1787 | 使所有区间的异或结果为零 | 位运算 数组 动态规划 | ||
| 0121 | 买卖股票的最佳时机 | JS | 数组 动态规划 | |
| 0122 | 买卖股票的最佳时机 II | JS | 贪心 数组 | |
| 0123 | 买卖股票的最佳时机 III | JS | 数组 动态规划 | |
| 0188 | 买卖股票的最佳时机 IV | JS | 数组 动态规划 | |
| 0309 | 最佳买卖股票时机含冷冻期 | JS | 数组 动态规划 | |
| 0714 | 买卖股票的最佳时机含手续费 | JS | 贪心 数组 |
- 双串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1143 | 最长公共子序列 | JS | 字符串 动态规划 | |
| 0712 | 两个字符串的最小ASCII删除和 | JS | 字符串 动态规划 | |
| 0718 | 最长重复子数组 | 数组 二分查找 动态规划 3+ | ||
| 0583 | 两个字符串的删除操作 | JS | 字符串 动态规划 | |
| 0072 | 编辑距离 | JS | 字符串 动态规划 | |
| 0044 | 通配符匹配 | JS | 贪心 递归 字符串 1+ | |
| 0010 | 正则表达式匹配 | JS | 递归 字符串 动态规划 | |
| 0097 | 交错字符串 | 字符串 动态规划 | ||
| 0115 | 不同的子序列 | 字符串 动态规划 | ||
| 0087 | 扰乱字符串 | 字符串 动态规划 |
- 矩阵线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0118 | 杨辉三角 | 数组 动态规划 | ||
| 0119 | 杨辉三角 II | 数组 动态规划 | ||
| 0120 | 三角形最小路径和 | JS | 数组 动态规划 | |
| 0064 | 最小路径和 | JS | 数组 动态规划 矩阵 | |
| 0174 | 地下城游戏 | JS | 数组 动态规划 矩阵 | |
| 0221 | 最大正方形 | JS | 数组 动态规划 矩阵 | |
| 0931 | 下降路径最小和 | JS | 数组 动态规划 矩阵 | |
| 0576 | 出界的路径数 | 动态规划 | ||
| 0085 | 最大矩形 | 栈 数组 动态规划 2+ | ||
| 0363 | 矩形区域不超过 K 的最大数值和 | 数组 二分查找 矩阵 2+ | ||
| 面试题 17.24 | 最大子矩阵 | 数组 动态规划 矩阵 1+ | ||
| 1444 | 切披萨的方案数 | 记忆化搜索 数组 动态规划 1+ |
- 无串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1137 | 第 N 个泰波那契数 | JS | 记忆化搜索 数学 动态规划 | |
| 0650 | 只有两个键的键盘 | 数学 动态规划 | ||
| 0264 | 丑数 II | 哈希表 数学 动态规划 1+ | ||
| 0279 | 完全平方数 | JS | 广度优先搜索 数学 动态规划 | |
| 0343 | 整数拆分 | JS | 数学 动态规划 |
背包问题
- 0-1 背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0416 | 分割等和子集 | JS | 数组 动态规划 | |
| 0494 | 目标和 | JS | 数组 动态规划 回溯 | |
| 1049 | 最后一块石头的重量 II | JS | 数组 动态规划 |
- 完全背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0279 | 完全平方数 | JS | 广度优先搜索 数学 动态规划 | |
| 0322 | 零钱兑换 | JS | 广度优先搜索 数组 动态规划 | |
| 0518 | 零钱兑换 II | JS | 数组 动态规划 | |
| 0139 | 单词拆分 | JS | 字典树 记忆化搜索 数组 3+ | |
| 0377 | 组合总和 Ⅳ | 数组 动态规划 | ||
| 0638 | 大礼包 | 位运算 记忆化搜索 数组 3+ | ||
| 1449 | 数位成本和为目标值的最大数字 | 数组 动态规划 |
多重背包问题
分组背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1155 | 掷骰子等于目标和的方法数 | 动态规划 | ||
| 2585 | 获得分数的方法数 | 数组 动态规划 |
- 多维背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0474 | 一和零 | JS | 数组 字符串 动态规划 | |
| 0879 | 盈利计划 | 数组 动态规划 | ||
| 1995 | 统计特殊四元组 | 数组 枚举 |
区间 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0486 | 预测赢家 | 递归 数组 数学 2+ | ||
| 0312 | 戳气球 | 数组 动态规划 | ||
| 0877 | 石子游戏 | 数组 数学 动态规划 1+ | ||
| 1000 | 合并石头的最低成本 | 数组 动态规划 前缀和 | ||
| 1547 | 切棍子的最小成本 | 数组 动态规划 排序 | ||
| 0664 | 奇怪的打印机 | 字符串 动态规划 | ||
| 1039 | 多边形三角剖分的最低得分 | 数组 动态规划 | ||
| 0546 | 移除盒子 | 记忆化搜索 数组 动态规划 | ||
| 0375 | 猜数字大小 II | JS | 数学 动态规划 博弈 | |
| 0678 | 有效的括号字符串 | JS | 栈 贪心 字符串 1+ | |
| 0005 | 最长回文子串 | JS | 字符串 动态规划 | |
| 0516 | 最长回文子序列 | JS | 字符串 动态规划 | |
| 0730 | 统计不同回文子序列 | 字符串 动态规划 | ||
| 2104 | 子数组范围和 | 栈 数组 单调栈 |
树形 DP
- 固定根的树形 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0543 | 二叉树的直径 | JS | 树 深度优先搜索 二叉树 | |
| 0124 | 二叉树中的最大路径和 | 树 深度优先搜索 动态规划 1+ | ||
| 1245 | 树的直径 | 树 深度优先搜索 广度优先搜索 2+ | ||
| 2246 | 相邻字符不同的最长路径 | 树 深度优先搜索 图 3+ | ||
| 0687 | 最长同值路径 | 树 深度优先搜索 二叉树 | ||
| 0337 | 打家劫舍 III | 树 深度优先搜索 动态规划 1+ | ||
| 0333 | 最大 BST 子树 | 树 深度优先搜索 二叉搜索树 2+ | ||
| 1617 | 统计子树中城市之间最大距离 | 位运算 树 动态规划 2+ | ||
| 2538 | 最大价值和与最小价值和的差值 | 树 深度优先搜索 数组 1+ | ||
| 1569 | 将子数组重新排序得到同一个二叉搜索树的方案数 | 树 并查集 二叉搜索树 7+ | ||
| 1372 | 二叉树中的最长交错路径 | 树 深度优先搜索 动态规划 1+ | ||
| 1373 | 二叉搜索子树的最大键值和 | 树 深度优先搜索 二叉搜索树 2+ | ||
| 0968 | 监控二叉树 | 树 深度优先搜索 动态规划 1+ | ||
| 1273 | 删除树节点 | 树 深度优先搜索 广度优先搜索 | ||
| 1519 | 子树中标签相同的节点数 | 树 深度优先搜索 广度优先搜索 2+ |
- 不定根的树形 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0310 | 最小高度树 | 深度优先搜索 广度优先搜索 图 1+ | ||
| 0834 | 树中距离之和 | 树 深度优先搜索 图 1+ | ||
| 2581 | 统计可能的树根数目 | 树 深度优先搜索 哈希表 1+ |
状态压缩 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1879 | 两个数组最小的异或值之和 | 位运算 数组 动态规划 1+ | ||
| 2172 | 数组的最大与和 | 位运算 数组 动态规划 1+ | ||
| 1947 | 最大兼容性评分和 | 位运算 数组 动态规划 2+ | ||
| 1595 | 连通两组点的最小成本 | 位运算 数组 动态规划 2+ | ||
| 1494 | 并行课程 II | 位运算 图 动态规划 1+ | ||
| 1655 | 分配重复整数 | 位运算 数组 动态规划 2+ | ||
| 1986 | 完成任务的最少工作时间段 | 位运算 数组 动态规划 2+ | ||
| 1434 | 每个人戴不同帽子的方案数 | 位运算 数组 动态规划 1+ | ||
| 1799 | N 次操作后的最大分数和 | 位运算 数组 数学 4+ | ||
| 1681 | 最小不兼容性 | 位运算 数组 动态规划 1+ | ||
| 0526 | 优美的排列 | 位运算 数组 动态规划 2+ | ||
| 0351 | 安卓系统手势解锁 | 动态规划 回溯 | ||
| 0464 | 我能赢吗 | 位运算 记忆化搜索 数学 3+ | ||
| 0847 | 访问所有节点的最短路径 | 位运算 广度优先搜索 图 2+ | ||
| 0638 | 大礼包 | 位运算 记忆化搜索 数组 3+ | ||
| 1994 | 好子集的数目 | 位运算 数组 数学 2+ | ||
| 1349 | 参加考试的最大学生数 | 位运算 数组 动态规划 2+ | ||
| 0698 | 划分为k个相等的子集 | 位运算 记忆化搜索 数组 3+ | ||
| 0943 | 最短超级串 | 位运算 数组 字符串 2+ | ||
| 0691 | 贴纸拼词 | 位运算 数组 字符串 3+ | ||
| 0982 | 按位与为零的三元组 | 位运算 数组 哈希表 |
计数 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0062 | 不同路径 | JS | 数学 动态规划 组合数学 | |
| 0063 | 不同路径 II | JS | 数组 动态规划 矩阵 | |
| 0343 | 整数拆分 | JS | 数学 动态规划 | |
| 0096 | 不同的二叉搜索树 | JS | 树 二叉搜索树 数学 2+ | |
| 1259 | 不相交的握手 | 数学 动态规划 | ||
| 0790 | 多米诺和托米诺平铺 | 动态规划 | ||
| 0070 | 爬楼梯 | JS | 记忆化搜索 数学 动态规划 | |
| 0746 | 使用最小花费爬楼梯 | 数组 动态规划 | ||
| 0509 | 斐波那契数 | JS | 递归 记忆化搜索 数学 1+ | |
| 1137 | 第 N 个泰波那契数 | JS | 记忆化搜索 数学 动态规划 |
数位 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 2376 | 统计特殊整数 | 数学 动态规划 | ||
| 0357 | 统计各位数字都不同的数字个数 | 数学 动态规划 回溯 | ||
| 1012 | 至少有 1 位重复的数字 | 数学 动态规划 | ||
| 0902 | 最大为 N 的数字组合 | 数组 数学 字符串 2+ | ||
| 0788 | 旋转数字 | 数学 动态规划 | ||
| 0600 | 不含连续1的非负整数 | 动态规划 | ||
| 0233 | 数字 1 的个数 | 递归 数学 动态规划 | ||
| 2719 | 统计整数数目 | 数学 字符串 动态规划 | ||
| 0248 | 中心对称数 III | 递归 数组 字符串 | ||
| 1088 | 易混淆数 II | 数学 回溯 | ||
| 1067 | 范围内的数字计数 | 数学 动态规划 | ||
| 1742 | 盒子中小球的最大数量 | 哈希表 数学 计数 | ||
| 面试题 17.06 | 2出现的次数 | 递归 数学 动态规划 |
概率 DP
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0688 | 骑士在棋盘上的概率 | 动态规划 | ||
| 0808 | 分汤 | 数学 动态规划 概率与统计 | ||
| 0837 | 新 21 点 | 数学 动态规划 滑动窗口 1+ | ||
| 1230 | 抛掷硬币 | 数学 动态规划 概率与统计 | ||
| 1467 | 两个盒子中球的颜色数相同的概率 | 数组 数学 动态规划 3+ | ||
| 1227 | 飞机座位分配概率 | 脑筋急转弯 数学 动态规划 1+ | ||
| 1377 | T 秒后青蛙的位置 | 树 深度优先搜索 广度优先搜索 1+ | ||
| 剑指 Offer 60 | n个骰子的点数 | 数学 动态规划 概率与统计 |