#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个骰子的点数		数学、动态规划、概率与统计	中等

#