算法：动态规划题目

动态规划基础题目

题号	标题	标签	难度
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	统计可能的树根数目	树、深度优先搜索、哈希表、动态规划	困难