动态规划基础题目
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0509 | 斐波那契数 | 递归、记忆化搜索、数学、动态规划 | 简单 | |
| 0070 | 爬楼梯 | 记忆化搜索、数学、动态规划 | 简单 | |
| 0062 | 不同路径 | 数学、动态规划、组合数学 | 中等 |
记忆化搜索题目
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1137 | 第 N 个泰波那契数 | 记忆化搜索、数学、动态规划 | 简单 | |
| 0375 | 猜数字大小 II | 数学、动态规划、博弈 | 中等 | |
| 0494 | 目标和 | 数组、动态规划、回溯 | 中等 | |
| 0576 | 出界的路径数 | 动态规划 | 中等 | |
| 0087 | 扰乱字符串 | 字符串、动态规划 | 困难 | |
| 0403 | 青蛙过河 | 数组、动态规划 | 困难 | |
| 0552 | 学生出勤记录 II | 动态规划 | 困难 | |
| 0913 | 猫和老鼠 | 图、拓扑排序、记忆化搜索、数学、动态规划、博弈 | 困难 | |
| 0329 | 矩阵中的最长递增路径 | 深度优先搜索、广度优先搜索、图、拓扑排序、记忆化搜索、数组、动态规划、矩阵 | 困难 |
单串线性DP问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0300 | 最长递增子序列 | 数组、二分查找、动态规划 | 中等 | |
| 0673 | 最长递增子序列的个数 | 树状数组、线段树、数组、动态规划 | 中等 | |
| 0354 | 俄罗斯套娃信封问题 | 数组、二分查找、动态规划、排序 | 困难 | |
| 0053 | 最大子数组和 | 数组、分治、动态规划 | 中等 | |
| 0152 | 乘积最大子数组 | 数组、动态规划 | 中等 | |
| 0918 | 环形子数组的最大和 | 队列、数组、分治、动态规划、单调队列 | 中等 | |
| 0198 | 打家劫舍 | 数组、动态规划 | 中等 | |
| 0213 | 打家劫舍 II | 数组、动态规划 | 中等 | |
| 0740 | 删除并获得点数 | 数组、哈希表、动态规划 | 中等 | |
| 1388 | 3n 块披萨 | 贪心、数组、动态规划、堆（优先队列） | 困难 | |
| 0873 | 最长的斐波那契子序列的长度 | 数组、哈希表、动态规划 | 中等 | |
| 1027 | 最长等差数列 | 数组、哈希表、二分查找、动态规划 | 中等 | |
| 1055 | 形成字符串的最短路径 | 贪心、双指针、字符串 | 中等 | |
| 0368 | 最大整除子集 | 数组、数学、动态规划、排序 | 中等 | |
| 0032 | 最长有效括号 | 栈、字符串、动态规划 | 困难 | |
| 0413 | 等差数列划分 | 数组、动态规划 | 中等 | |
| 0091 | 解码方法 | 字符串、动态规划 | 中等 | |
| 0639 | 解码方法 II | 字符串、动态规划 | 困难 | |
| 0132 | 分割回文串 II | 字符串、动态规划 | 困难 | |
| 1220 | 统计元音字母序列的数目 | 动态规划 | 困难 | |
| 0338 | 比特位计数 | 位运算、动态规划 | 简单 | |
| 0801 | 使序列递增的最小交换次数 | 数组、动态规划 | 困难 | |
| 0871 | 最低加油次数 | 贪心、数组、动态规划、堆（优先队列） | 困难 | |
| 0045 | 跳跃游戏 II | 贪心、数组、动态规划 | 中等 | |
| 0813 | 最大平均值和的分组 | 数组、动态规划、前缀和 | 中等 | |
| 0887 | 鸡蛋掉落 | 数学、二分查找、动态规划 | 困难 | |
| 0256 | 粉刷房子 | 数组、动态规划 | 中等 | |
| 0265 | 粉刷房子 II | 数组、动态规划 | 困难 | |
| 1473 | 粉刷房子 III | 数组、动态规划 | 困难 | |
| 0975 | 奇偶跳 | 栈、数组、动态规划、有序集合、单调栈 | 困难 | |
| 0403 | 青蛙过河 | 数组、动态规划 | 困难 | |
| 1478 | 安排邮筒 | 数组、数学、动态规划、排序 | 困难 | |
| 1230 | 抛掷硬币 | 数学、动态规划、概率与统计 | 中等 | |
| 0410 | 分割数组的最大值 | 贪心、数组、二分查找、动态规划、前缀和 | 困难 | |
| 1751 | 最多可以参加的会议数目 II | 数组、二分查找、动态规划、排序 | 困难 | |
| 1787 | 使所有区间的异或结果为零 | 位运算、数组、动态规划 | 困难 | |
| 0121 | 买卖股票的最佳时机 | 数组、动态规划 | 简单 | |
| 0122 | 买卖股票的最佳时机 II | 贪心、数组 | 中等 | |
| 0123 | 买卖股票的最佳时机 III | 数组、动态规划 | 困难 | |
| 0188 | 买卖股票的最佳时机 IV | 数组、动态规划 | 困难 | |
| 0309 | 最佳买卖股票时机含冷冻期 | 数组、动态规划 | 中等 | |
| 0714 | 买卖股票的最佳时机含手续费 | 贪心、数组 | 中等 |
双串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1143 | 最长公共子序列 | 字符串、动态规划 | 中等 | |
| 0712 | 两个字符串的最小ASCII删除和 | 字符串、动态规划 | 中等 | |
| 0718 | 最长重复子数组 | 数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希 | 中等 | |
| 0583 | 两个字符串的删除操作 | 字符串、动态规划 | 中等 | |
| 0072 | 编辑距离 | 字符串、动态规划 | 困难 | |
| 0044 | 通配符匹配 | 贪心、递归、字符串、动态规划 | 困难 | |
| 0010 | 正则表达式匹配 | 递归、字符串、动态规划 | 困难 | |
| 0097 | 交错字符串 | 字符串、动态规划 | 中等 | |
| 0115 | 不同的子序列 | 字符串、动态规划 | 困难 | |
| 0087 | 扰乱字符串 | 字符串、动态规划 | 困难 |
矩阵线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0118 | 杨辉三角 | 数组、动态规划 | 简单 | |
| 0119 | 杨辉三角 II | 数组、动态规划 | 简单 | |
| 0120 | 三角形最小路径和 | 数组、动态规划 | 中等 | |
| 0064 | 最小路径和 | 数组、动态规划、矩阵 | 中等 | |
| 0174 | 地下城游戏 | 数组、动态规划、矩阵 | 困难 | |
| 0221 | 最大正方形 | 数组、动态规划、矩阵 | 中等 | |
| 0931 | 下降路径最小 | 数组、动态规划、矩阵 | 中等 | |
| 0576 | 出界的路径数 | 动态规划 | 中等 | |
| 0085 | 最大矩形 | 栈、数组、动态规划、矩阵、单调栈 | 困难 | |
| 0363 | 矩形区域不超过 K 的最大数值和 | 数组、二分查找、矩阵、有序集合、前缀和 | 困难 | |
| 面试题 17.24 | 最大子矩阵 | 数组、动态规划、矩阵、前缀和 | 困难 | |
| 1444 | 切披萨的方案数 | 记忆化搜索、数组、动态规划、矩阵 | 困难 |
无串线性 DP 问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1137 | 第 N 个泰波那契数 | 记忆化搜索、数学、动态规划 | 简单 | |
| 0650 | 只有两个键的键盘 | 数学、动态规划 | 中等 | |
| 0264 | 丑数 II | 哈希表、数学、动态规划、堆（优先队列） | 中等 | |
| 0279 | 完全平方数 | 广度优先搜索、数学、动态规划 | 中等 | |
| 0343 | 整数拆分 | 数学、动态规划 | 中等 |
0-1 背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0416 | 分割等和子集 | 数组、动态规划 | 中等 | |
| 0494 | 目标和 | 数组、动态规划、回溯 | 中等 | |
| 1049 | 最后一块石头的重量 II | 数组、动态规划 | 中等 |
完全背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0279 | 完全平方数 | 广度优先搜索、数学、动态规划 | 中等 | |
| 0322 | 零钱兑换 | 广度优先搜索、数组、动态规划 | 中等 | |
| 0518 | 零钱兑换 II | 数组、动态规划 | 中等 | |
| 0139 | 单词拆分 | 字典树、记忆化搜索、数组、哈希表、字符串、动态规划 | 中等 | |
| 0377 | 组合总和 Ⅳ | 数组、动态规划 | 中等 | |
| 0638 | 大礼包 | 位运算、记忆化搜索、数组、动态规划、回溯、状态压缩 | 中等 | |
| 1449 | 数位成本和为目标值的最大数字 | 数组、动态规划 | 困难 |
多重背包问题
分组背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 1155 | 掷骰子等于目标和的方法数 | 动态规划 | 中等 | |
| 2585 | 获得分数的方法数 | 数组、动态规划 | 困难 |
多维背包问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0474 | 一和零 | 数组、字符串、动态规划 | 中等 | |
| 0879 | 盈利计划 | 数组、动态规划 | 困难 | |
| 1995 | 统计特殊四元组 | 数组、枚举 | 简单 |
区间DP问题
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0486 | 预测赢家 | 递归、数组、数学、动态规划、博弈 | 中等 | |
| 0312 | 戳气球 | 数组、动态规划 | 困难 | |
| 0877 | 石子游戏 | 数组、数学、动态规划、博弈 | 中等 | |
| 1000 | 合并石头的最低成本 | 数组、动态规划、前缀和 | 困难 | |
| 1547 | 切棍子的最小成本 | 数组、动态规划、排序 | 困难 | |
| 0664 | 奇怪的打印机 | 字符串、动态规划 | 困难 | |
| 1039 | 多边形三角剖分的最低得分 | 数组、动态规划 | 中等 | |
| 0546 | 移除盒子 | 记忆化搜索、数组、动态规划 | 困难 | |
| 0375 | 猜数字大小 II | 数学、动态规划、博弈 | 中等 | |
| 0678 | 有效的括号字符串 | 栈、贪心、字符串、动态规划 | 中等 | |
| 0005 | 最长回文子串 | 字符串、动态规划 | 中等 | |
| 0516 | 最长回文子序列 | 字符串、动态规划 | 中等 | |
| 0730 | 统计不同回文子序列 | 字符串、动态规划 | 困难 | |
| 2104 | 子数组范围和 | 栈、数组、单调栈 | 中等 |
固定根的树形 DP 题目
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0543 | 二叉树的直径 | 树、深度优先搜索、二叉树 | 简单 | |
| 0124 | 二叉树中的最大路径和 | 树、深度优先搜索、动态规划、二叉树 | 困难 | |
| 1245 | 树的直径 | 树、深度优先搜索、广度优先搜索、图、拓扑排序 | 中等 | |
| 2246 | 相邻字符不同的最长路径 | 树、深度优先搜索、图、拓扑排序、数组、字符串 | 困难 | |
| 0687 | 最长同值路径 | 树、深度优先搜索、二叉树 | 中等 | |
| 0337 | 打家劫舍 III | 树、深度优先搜索、动态规划、二叉树 | 中等 | |
| 0333 | 最大 BST 子树 | 树、深度优先搜索、二叉搜索树、动态规划、二叉树 | 中等 | |
| 1617 | 统计子树中城市之间最大距离 | 位运算、树、动态规划、状态压缩、枚举 | 困难 | |
| 2538 | 最大价值和与最小价值和的差值 | 树、深度优先搜索、数组、动态规划 | 困难 | |
| 1569 | 将子数组重新排序得到同一个二叉搜索树的方案数 | 树、并查集、二叉搜索树、记忆化搜索、数组、数学、分治、动态规划、二叉树、组合数学 | 困难 | |
| 1372 | 二叉树中的最长交错路径 | 树、深度优先搜索、动态规划、二叉树 | 中等 | |
| 1373 | 二叉搜索子树的最大键值和 | 树、深度优先搜索、二叉搜索树、动态规划、二叉树 | 困难 | |
| 0968 | 监控二叉树 | 树、深度优先搜索、动态规划、二叉树 | 困难 | |
| 1273 | 删除树节点 | 树、深度优先搜索、广度优先搜索 | 中等 | |
| 1519 | 子树中标签相同的节点数 | 树、深度优先搜索、广度优先搜索、哈希表、计数 | 中等 |
不定根的树形 DP 题目
| 题号 | 标题 | 题解 | 标签 | 难度 |
|---|---|---|---|---|
| 0310 | 最小高度树 | 深度优先搜索、广度优先搜索、图、拓扑排序 | 中等 | |
| 0834 | 树中距离之和 | 树、深度优先搜索、图、动态规划 | 困难 | |
| 2581 | 统计可能的树根数目 | 树、深度优先搜索、哈希表、动态规划 | 困难 |