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 | JS | 贪心 数组 动态规划 | |
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 | JS | 哈希表 数学 动态规划 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个骰子的点数 | 数学 动态规划 概率与统计 |