#10. 动态规划

#动态规划基础题目

题号 标题 题解 标签 难度
0509 斐波那契数 Python 递归、记忆化搜索、数学、动态规划 简单
0070 爬楼梯 Python 记忆化搜索、数学、动态规划
0062 不同路径 Python 数学、动态规划、组合数学 中等

#记忆化搜索题目

题号 标题 题解 标签 难度
1137 第 N 个泰波那契数 Python 记忆化搜索、数学、动态规划 简单
0375 猜数字大小 II Python 数学、动态规划、博弈 中等
0494 目标和 Python 数组、动态规划、回溯
0576 出界的路径数 Python 动态规划
0087 扰乱字符串 字符串、动态规划 困难
0403 青蛙过河 Python 数组、动态规划
0552 学生出勤记录 II 动态规划
0913 猫和老鼠 图、拓扑排序、记忆化搜索、数学、动态规划、博弈
0329 矩阵中的最长递增路径 Python 深度优先搜索、广度优先搜索、图、拓扑排序、记忆化搜索、数组、动态规划、矩阵

#线性 DP 题目

#单串线性 DP 问题

题号 标题 题解 标签 难度
0300 最长递增子序列 Python 数组、二分查找、动态规划 中等
0673 最长递增子序列的个数 Python 树状数组、线段树、数组、动态规划
0354 俄罗斯套娃信封问题 Python 数组、二分查找、动态规划、排序 困难
0053 最大子数组和 Python 数组、分治、动态规划 中等
0152 乘积最大子数组 Python 数组、动态规划
0918 环形子数组的最大和 Python 队列、数组、分治、动态规划、单调队列
0198 打家劫舍 Python 数组、动态规划
0213 打家劫舍 II Python
0740 删除并获得点数 数组、哈希表、动态规划
1388 3n 块披萨 贪心、数组、动态规划、堆(优先队列) 困难
0873 最长的斐波那契子序列的长度 Python 数组、哈希表、动态规划 中等
1027 最长等差数列 数组、哈希表、二分查找、动态规划
1055 形成字符串的最短路径 贪心、双指针、字符串
0368 最大整除子集 数组、数学、动态规划、排序
0032 最长有效括号 Python 栈、字符串、动态规划 困难
0413 等差数列划分 数组、动态规划 中等
0091 解码方法 Python 字符串、动态规划
0639 解码方法 II Python 困难
0132 分割回文串 II
1220 统计元音字母序列的数目 Python 动态规划
0338 比特位计数 Python 位运算、动态规划 简单
0801 使序列递增的最小交换次数 Python 数组、动态规划 困难
0871 最低加油次数 贪心、数组、动态规划、堆(优先队列)
0045 跳跃游戏 II Python 贪心、数组、动态规划 中等
0813 最大平均值和的分组 数组、动态规划、前缀和
0887 鸡蛋掉落 Python 数学、二分查找、动态规划 困难
0256 粉刷房子 数组、动态规划 中等
0265 粉刷房子 II 困难
1473 粉刷房子 III
0975 奇偶跳 栈、数组、动态规划、有序集合、单调栈
0403 青蛙过河 Python 数组、动态规划
1478 安排邮筒 数组、数学、动态规划、排序
1230 抛掷硬币 数学、动态规划、概率与统计 中等
0410 分割数组的最大值 Python 贪心、数组、二分查找、动态规划、前缀和 困难
1751 最多可以参加的会议数目 II 数组、二分查找、动态规划、排序
1787 使所有区间的异或结果为零 位运算、数组、动态规划
0121 买卖股票的最佳时机 Python 数组、动态规划 简单
0122 买卖股票的最佳时机 II Python 贪心、数组 中等
0123 买卖股票的最佳时机 III Python 数组、动态规划 困难
0188 买卖股票的最佳时机 IV Python
0309 最佳买卖股票时机含冷冻期 Python 中等
0714 买卖股票的最佳时机含手续费 Python 贪心、数组

#双串线性 DP 问题

题号 标题 题解 标签 难度
1143 最长公共子序列 Python 字符串、动态规划 中等
0712 两个字符串的最小ASCII删除和
0718 最长重复子数组 Python 数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希
0583 两个字符串的删除操作 Python 字符串、动态规划
0072 编辑距离 Python 困难
0044 通配符匹配 Python 贪心、递归、字符串、动态规划
0010 正则表达式匹配 Python 递归、字符串、动态规划
0097 交错字符串 字符串、动态规划 中等
0115 不同的子序列 Python 困难
0087 扰乱字符串

#矩阵线性 DP 问题

题号 标题 题解 标签 难度
0118 杨辉三角 Python 数组、动态规划 简单
0119 杨辉三角 II Python
0120 三角形最小路径和 Python 中等
0064 最小路径和 Python 数组、动态规划、矩阵
0174 地下城游戏 困难
0221 最大正方形 Python 中等
0931 下降路径最小和
0576 出界的路径数 Python 动态规划
0085 最大矩形 栈、数组、动态规划、矩阵、单调栈 困难
0363 矩形区域不超过 K 的最大数值和 数组、二分查找、矩阵、有序集合、前缀和
面试题 17.24 最大子矩阵 数组、动态规划、矩阵、前缀和
1444 切披萨的方案数 记忆化搜索、数组、动态规划、矩阵

#无串线性 DP 问题

题号 标题 题解 标签 难度
1137 第 N 个泰波那契数 Python 记忆化搜索、数学、动态规划 简单
0650 只有两个键的键盘 Python 数学、动态规划 中等
0264 丑数 II Python 哈希表、数学、动态规划、堆(优先队列)
0279 完全平方数 Python 广度优先搜索、数学、动态规划
0343 整数拆分 Python 数学、动态规划

#背包问题题目

#0-1 背包问题

题号 标题 题解 标签 难度
0416 分割等和子集 Python 数组、动态规划 中等
0494 目标和 Python 数组、动态规划、回溯
1049 最后一块石头的重量 II Python 数组、动态规划

#完全背包问题

题号 标题 题解 标签 难度
0279 完全平方数 Python 广度优先搜索、数学、动态规划 中等
0322 零钱兑换 Python 广度优先搜索、数组、动态规划
0518 零钱兑换 II Python 数组、动态规划
0139 单词拆分 Python 字典树、记忆化搜索、数组、哈希表、字符串、动态规划
0377 组合总和 Ⅳ Python 数组、动态规划
0638 大礼包 位运算、记忆化搜索、数组、动态规划、回溯、状态压缩
1449 数位成本和为目标值的最大数字 Python 数组、动态规划 困难

#多重背包问题

#分组背包问题

题号 标题 题解 标签 难度
1155 掷骰子等于目标和的方法数 Python 动态规划 中等
2585 获得分数的方法数 Python 数组、动态规划 困难

#多维背包问题

题号 标题 题解 标签 难度
0474 一和零 Python 数组、字符串、动态规划 中等
0879 盈利计划 数组、动态规划 困难
1995 统计特殊四元组 数组、枚举 简单

#区间 DP 题目

题号 标题 题解 标签 难度
0486 预测赢家 Python 递归、数组、数学、动态规划、博弈 中等
0312 戳气球 Python 数组、动态规划 困难
0877 石子游戏 Python 数组、数学、动态规划、博弈 中等
1000 合并石头的最低成本 Python 数组、动态规划、前缀和 困难
1547 切棍子的最小成本 Python 数组、动态规划、排序
0664 奇怪的打印机 Python 字符串、动态规划
1039 多边形三角剖分的最低得分 Python 数组、动态规划 中等
0546 移除盒子 Python 记忆化搜索、数组、动态规划 困难
0375 猜数字大小 II Python 数学、动态规划、博弈 中等
0678 有效的括号字符串 Python 栈、贪心、字符串、动态规划
0005 最长回文子串 Python 字符串、动态规划
0516 最长回文子序列 Python
0730 统计不同回文子序列 困难
2104 子数组范围和 栈、数组、单调栈 中等

#树形 DP 题目

#固定根的树形 DP 题目

题号 标题 题解 标签 难度
0543 二叉树的直径 Python 树、深度优先搜索、二叉树 简单
0124 二叉树中的最大路径和 Python 树、深度优先搜索、动态规划、二叉树 困难
1245 树的直径 Python 树、深度优先搜索、广度优先搜索、图、拓扑排序 中等
2246 相邻字符不同的最长路径 Python 树、深度优先搜索、图、拓扑排序、数组、字符串 困难
0687 最长同值路径 Python 树、深度优先搜索、二叉树 中等
0337 打家劫舍 III Python 树、深度优先搜索、动态规划、二叉树
0333 最大 BST 子树 树、深度优先搜索、二叉搜索树、动态规划、二叉树
1617 统计子树中城市之间最大距离 Python 位运算、树、动态规划、状态压缩、枚举 困难
2538 最大价值和与最小价值和的差值 Python 树、深度优先搜索、数组、动态规划
1569 将子数组重新排序得到同一个二叉搜索树的方案数 树、并查集、二叉搜索树、记忆化搜索、数组、数学、分治、动态规划、二叉树、组合数学
1372 二叉树中的最长交错路径 树、深度优先搜索、动态规划、二叉树 中等
1373 二叉搜索子树的最大键值和 树、深度优先搜索、二叉搜索树、动态规划、二叉树 困难
0968 监控二叉树 Python 树、深度优先搜索、动态规划、二叉树
1273 删除树节点 树、深度优先搜索、广度优先搜索 中等
1519 子树中标签相同的节点数 树、深度优先搜索、广度优先搜索、哈希表、计数

#不定根的树形 DP 题目

题号 标题 题解 标签 难度
0310 最小高度树 Python 深度优先搜索、广度优先搜索、图、拓扑排序 中等
0834 树中距离之和 Python 树、深度优先搜索、图、动态规划 困难
2581 统计可能的树根数目 树、深度优先搜索、哈希表、动态规划

#状态压缩 DP 题目

题号 标题 题解 标签 难度
1879 两个数组最小的异或值之和 Python 位运算、数组、动态规划、状态压缩 困难
2172 数组的最大与和 Python
1947 最大兼容性评分和 Python 位运算、数组、动态规划、回溯、状态压缩 中等
1595 连通两组点的最小成本 Python 位运算、数组、动态规划、状态压缩、矩阵 困难
1494 并行课程 II 位运算、图、动态规划、状态压缩
1655 分配重复整数 位运算、数组、动态规划、回溯、状态压缩
1986 完成任务的最少工作时间段 Python 中等
1434 每个人戴不同帽子的方案数 位运算、数组、动态规划、状态压缩 困难
1799 N 次操作后的最大分数和 位运算、数组、数学、动态规划、回溯、状态压缩、数论
1681 最小不兼容性 位运算、数组、动态规划、状态压缩
0526 优美的排列 Python 位运算、数组、动态规划、回溯、状态压缩 中等
0351 安卓系统手势解锁 Python 动态规划、回溯
0464 我能赢吗 Python 位运算、记忆化搜索、数学、动态规划、状态压缩、博弈
0847 访问所有节点的最短路径 Python 位运算、广度优先搜索、图、动态规划、状态压缩 困难
0638 大礼包 位运算、记忆化搜索、数组、动态规划、回溯、状态压缩 中等
1994 好子集的数目 Python 位运算、数组、数学、动态规划、状态压缩 困难
1349 参加考试的最大学生数 Python 位运算、数组、动态规划、状态压缩、矩阵
0698 划分为k个相等的子集 Python 位运算、记忆化搜索、数组、动态规划、回溯、状态压缩 中等
0943 最短超级串 位运算、数组、字符串、动态规划、状态压缩 困难
0691 贴纸拼词 Python 位运算、数组、字符串、动态规划、回溯、状态压缩
0982 按位与为零的三元组 Python 位运算、数组、哈希表

#计数 DP 题目

题号 标题 题解 标签 难度
0062 不同路径 Python 数学、动态规划、组合数学 中等
0063 不同路径 II Python 数组、动态规划、矩阵
0343 整数拆分 Python 数学、动态规划
0096 不同的二叉搜索树 Python 树、二叉搜索树、数学、动态规划、二叉树
1259 不相交的握手 数学、动态规划 困难
0790 多米诺和托米诺平铺 动态规划 中等
0070 爬楼梯 Python 记忆化搜索、数学、动态规划 简单
0746 使用最小花费爬楼梯 Python 数组、动态规划
0509 斐波那契数 Python 递归、记忆化搜索、数学、动态规划
1137 第 N 个泰波那契数 Python 记忆化搜索、数学、动态规划

#数位 DP 题目

题号 标题 题解 标签 难度
2376 统计特殊整数 Python 数学、动态规划 困难
0357 统计各位数字都不同的数字个数 Python 数学、动态规划、回溯 中等
1012 至少有 1 位重复的数字 Python 数学、动态规划 困难
0902 最大为 N 的数字组合 Python 数组、数学、字符串、二分查找、动态规划
0788 旋转数字 Python 数学、动态规划 中等
0600 不含连续1的非负整数 Python 动态规划 困难
0233 数字 1 的个数 Python 递归、数学、动态规划
2719 统计整数数目 Python 数学、字符串、动态规划
0248 中心对称数 III 递归、数组、字符串
1088 易混淆数 II 数学、回溯
1067 范围内的数字计数 数学、动态规划
1742 盒子中小球的最大数量 Python 哈希表、数学、计数 简单
面试题 17.06 2出现的次数 Python 递归、数学、动态规划 困难

#概率 DP 题目

题号 标题 题解 标签 难度
0688 骑士在棋盘上的概率 Python 动态规划 中等
0808 分汤 数学、动态规划、概率与统计
0837 新 21 点 数学、动态规划、滑动窗口、概率与统计
1230 抛掷硬币 数学、动态规划、概率与统计
1467 两个盒子中球的颜色数相同的概率 数组、数学、动态规划、回溯、组合数学、概率与统计 困难
1227 飞机座位分配概率 Python 脑筋急转弯、数学、动态规划、概率与统计 中等
1377 T 秒后青蛙的位置 树、深度优先搜索、广度优先搜索、图 困难
剑指 Offer 60 n个骰子的点数 数学、动态规划、概率与统计 中等

#