动态规划
动态规划把问题拆成更小的同类问题，先求出小问题的答案再组合起来，并把答案存下来避免重复计算。最难的是想清楚“状态”代表什么，代码本身往往不长。
这是体量最大的题单，20 章共 465 道题。从入门 DP 和网格 DP 开始，接着是背包、LCS 与 LIS、划分型与状态机 DP，再往后是区间、状压、数位、树形、图上、博弈与概率 DP，另外还有输出具体方案、跳跃游戏变形等专题。适合已经能熟练写递归、想按顺序把 DP 从头练一遍的人。
465 道题难度分 1262–312520 章节
进入书房
想有人陪你把这份题单做完吗？登录后进入书房，女主角会一次递给你一道题。
一、入门 DP
§1.1 爬楼梯
| 题目 | 难度分 |
|---|---|
| 70. 爬楼梯 | 未评分 |
| 746. 使用最小花费爬楼梯 | 1500 |
| 3693. 爬楼梯 II | 1560 |
| 377. 组合总和 Ⅳ | 1600 |
| 2466. 统计构造好字符串的方案数 | 1694 |
| 2266. 统计打字方案数 | 1857 |
§1.2 打家劫舍
| 题目 | 难度分 |
|---|---|
| 198. 打家劫舍 | 未评分 |
| 213. 打家劫舍 II | 未评分 |
| 2320. 统计放置房子的方式数 | 1608 |
| 740. 删除并获得点数 | 未评分 |
| 3186. 施咒的最大总伤害 | 1841 |
| 2140. 解决智力问题 | 1709 |
§1.3 Maximum Subarray Sum（最大子段和）
| 题目 | 难度分 |
|---|---|
| 53. 最大子数组和 | 未评分 |
| 2606. 找到最大开销的子字符串 | 1422 |
| 1749. 任意子数组和的绝对值的最大值 | 1542 |
| 1191. K 次串联后最大子数组之和 | 1748 |
| 918. 环形子数组的最大和 | 1777 |
| 2321. 拼接数组的最大分数 | 1791 |
| 152. 乘积最大子数组 | 未评分 |
| 1186. 删除一次得到子数组最大和 | 1799 |
| 3381. 长度可被 K 整除的子数组的最大元素和 | 1943 |
二、Grid DP
§2.1 基础
| 题目 | 难度分 |
|---|---|
| 64. 最小路径和 | 未评分 |
| 62. 不同路径 | 未评分 |
| 63. 不同路径 II | 未评分 |
| 120. 三角形最小路径和 | 未评分 |
| 3393. 统计异或值为给定值的路径数目 | 1573 |
| 931. 下降路径最小和 | 1573 |
| 2684. 矩阵中移动的最大次数 | 1626 |
| 3603. 交替方向的最小路径代价 II | 1639 |
| 2304. 网格中的最小路径代价 | 1658 |
| 1289. 下降路径最小和 II | 1697 |
| 3418. 机器人可以获得的最大金币数 | 1798 |
| 3742. 网格中得分最大的路径 | 1804 |
| 1824. 最少侧跳次数 | 1778 |
§2.2 进阶
| 题目 | 难度分 |
|---|---|
| 1594. 矩阵的最大非负积 | 1807 |
| 1301. 最大得分的路径数目 | 1853 |
| 3665. 统计镜子反射路径数目 | 1883 |
| 2435. 矩阵中和能被 K 整除的路径 | 1952 |
| 174. 地下城游戏 | 未评分 |
| 329. 矩阵中的最长递增路径 | 未评分 |
| 2328. 网格图中递增路径的数目 | 2001 |
| 2267. 检查是否有合法括号字符串路径 | 2085 |
| 1937. 扣分后的最大得分 | 2106 |
| 3363. 最多可收集的水果数目 | 2200 |
| 1463. 摘樱桃 II | 未评分 |
| 741. 摘樱桃 | 未评分 |
| 3459. 最长 V 形对角线段的长度 | 2337 |
三、Knapsack DP
§3.1 0-1 Knapsack
| 题目 | 难度分 |
|---|---|
| 416. 分割等和子集 | 未评分 |
| 494. 目标和 | 未评分 |
| 2915. 和为目标值的最长子序列的长度 | 1659 |
| 2787. 将一个数字表示成幂的和的方案数 | 1818 |
| 3180. 执行操作可获得的最大总奖励 I | 1849 |
| 474. 一和零 | 未评分 |
| 3489. 零数组变换 IV | 2068 |
| 3685. 含上限元素的子序列和 | 2073 |
| 1049. 最后一块石头的重量 II | 2092 |
| 1774. 最接近目标价格的甜点成本 | 未评分 |
| 879. 盈利计划 | 2204 |
| 3082. 求出所有子序列的能量和 | 2242 |
| 956. 最高的广告牌 | 2381 |
| 2518. 好分区的数目 | 2415 |
| 2742. 给墙壁刷油漆 | 2425 |
| 3181. 执行操作可获得的最大总奖励 II | 2688 |
§3.2 Unbounded Knapsack
| 题目 | 难度分 |
|---|---|
| 322. 零钱兑换 | 未评分 |
| 518. 零钱兑换 II | 未评分 |
| 279. 完全平方数 | 未评分 |
| 3592. 硬币面值还原 | 1701 |
| 1449. 数位成本和为目标值的最大数字 | 1927 |
§3.3 Bounded Knapsack（选做）选做
| 题目 | 难度分 |
|---|---|
| 2585. 获得分数的方法数 | 1910 |
| 3333. 找到初始输入字符串 II | 2629 |
| 2902. 和带限制的子多重集合的数目 | 2759 |
| 3489. 零数组变换 IV | 未评分 |
§3.4 Grouped Knapsack
| 题目 | 难度分 |
|---|---|
| 1155. 掷骰子等于目标和的方法数 | 1654 |
| 1981. 最小化目标值与所选元素的差 | 2010 |
| 2218. 从栈中取出 K 个硬币的最大面值和 | 2158 |
§3.5 Tree Knapsack（选做）选做
| 题目 | 难度分 |
|---|---|
| 3562. 折扣价交易股票的最大利润 | 2458 |
四、经典Linear DP
§4.1 Longest Common Subsequence (LCS)
| 题目 | 难度分 |
|---|---|
| 1143. 最长公共子序列 | 未评分 |
| 583. 两个字符串的删除操作 | 未评分 |
| 712. 两个字符串的最小 ASCII 删除和 | 未评分 |
| 72. 编辑距离 | 未评分 |
| 1035. 不相交的线 | 1806 |
| 1458. 两个子序列的最大点积 | 1824 |
| 718. 最长重复子数组 | 未评分 |
| 3290. 最高乘法得分 | 1692 |
| 115. 不同的子序列 | 未评分 |
| 3628. 插入一个字母的最大子序列数 | 1754 |
| 3316. 从原字符串里进行删除操作的最多次数 | 2062 |
| 1639. 通过给定词典构造目标字符串的方案数 | 2082 |
| 97. 交错字符串 | 未评分 |
| 1092. 最短公共超序列 | 未评分 |
| 44. 通配符匹配 | 未评分 |
| 10. 正则表达式匹配 | 未评分 |
§4.2 Longest Increasing Subsequence (LIS)
| 题目 | 难度分 |
|---|---|
| 300. 最长递增子序列 | 未评分 |
| 334. 递增的三元子序列 | 未评分 |
| 2826. 将三个组排序 | 1721 |
| 1671. 得到山形数组的最少删除次数 | 1913 |
| 1964. 找出到每个位置为止最长的有效障碍赛跑路线 | 1933 |
| 2111. 使数组 K 递增的最少操作次数 | 1941 |
| 354. 俄罗斯套娃信封问题 | 未评分 |
| 1626. 无矛盾的最佳球队 | 2027 |
| 1691. 堆叠长方体的最大高度 | 2172 |
| 960. 删列造序 III | 2247 |
| 2407. 最长递增子序列 II | 2280 |
| 673. 最长递增子序列的个数 | 未评分 |
| 1187. 使数组严格递增 | 2316 |
| 1713. 得到子序列的最少操作次数 | 2351 |
| 3288. 最长上升路径的长度 | 2450 |
| 368. 最大整除子集 | 1800 |
| 2901. 最长相邻不相等子序列 II | 1899 |
五、Partition DP
§5.1 判定能否划分
| 题目 | 难度分 |
|---|---|
| 2369. 检查数组是否存在有效划分 | 1780 |
| 139. 单词拆分 | 未评分 |
§5.2 最优划分
| 题目 | 难度分 |
|---|---|
| 132. 分割回文串 II | 未评分 |
| 2707. 字符串中的额外字符 | 1736 |
| 3196. 最大化子数组的总成本 | 1847 |
| 2767. 将字符串分割为最少的美丽子字符串 | 1865 |
| 91. 解码方法 | 未评分 |
| 639. 解码方法 II | 未评分 |
| 1043. 分隔数组以得到最大和 | 1916 |
| 3144. 分割字符频率相等的最少子字符串 | 1917 |
| 1416. 恢复数组 | 1920 |
| 2472. 不重叠回文子字符串的最大数目 | 2013 |
| 1105. 填充书架 | 2014 |
| 2547. 拆分数组的最小代价 | 2020 |
| 3578. 统计极差最大为 K 的分割方式数 | 2033 |
| 2430. 对字母串可执行的最大删除数 | 2102 |
| 2463. 最小移动总距离 | 2454 |
| 3579. 字符串转换需要的最小操作数 | 2493 |
| 3500. 将数组分割为子数组的最小代价 | 2569 |
| 3441. 变成好标题的最少代价 | 2765 |
§5.3 约束划分个数
六、State Machine DP
§6.1 买卖股票
| 题目 | 难度分 |
|---|---|
| 121. 买卖股票的最佳时机 | 未评分 |
| 122. 买卖股票的最佳时机 II | 未评分 |
| 123. 买卖股票的最佳时机 III | 未评分 |
| 188. 买卖股票的最佳时机 IV | 未评分 |
| 3573. 买卖股票的最佳时机 V | 1777 |
| 309. 买卖股票的最佳时机含冷冻期 | 未评分 |
| 714. 买卖股票的最佳时机含手续费 | 未评分 |
§6.2 基础
| 题目 | 难度分 |
|---|---|
| 3259. 超级饮料的最大强化能量 | 1484 |
| 2222. 选择建筑的方案数 | 1657 |
| 2708. 一个小组的最大实力值 | 未评分 |
| 1567. 乘积为正数的最长子数组长度 | 1710 |
| 2786. 访问数组中的位置使分数最大 | 1733 |
| 1911. 最大交替子序列和 | 1786 |
| 376. 摆动序列 | 未评分 |
§6.3 进阶
| 题目 | 难度分 |
|---|---|
| 3628. 插入一个字母的最大子序列数 | 1754 |
| 2771. 构造最长非递减子数组 | 1792 |
| 1186. 删除一次得到子数组最大和 | 1799 |
| 1594. 矩阵的最大非负积 | 1807 |
| 3738. 替换至多一个元素后最长非递减子数组 | 1811 |
| 3196. 最大化子数组的总成本 | 1847 |
| 935. 骑士拨号器 | 未评分 |
| 1537. 最大得分 | 1961 |
| 2919. 使数组变美的最小增量运算数 | 2031 |
| 801. 使序列递增的最小交换次数 | 2066 |
| 3434. 子数组操作后的最大频率 | 2094 |
| 1955. 统计特殊子序列的数目 | 2125 |
| 3068. 最大节点价值之和 | 2268 |
| 3640. 三段式数组 II | 2278 |
| 2272. 最大波动的子字符串 | 2516 |
| 3661. 可以被机器人摧毁的最大墙壁数目 | 2525 |
| 3743. 循环划分的最大得分 | 3125 |
七、其他Linear DP
§7.1 一维 DP
| 题目 | 难度分 |
|---|---|
| 3147. 从魔法师身上吸取的最大能量 | 1460 |
| 2944. 购买水果需要的最少金币数 | 1709 |
| 2140. 解决智力问题 | 1709 |
| 983. 最低票价 | 1786 |
| 368. 最大整除子集 | 1800 |
| 2901. 最长相邻不相等子序列 II | 1899 |
| 650. 两个键的键盘 | 2000 |
| 871. 最低加油次数 | 2074 |
| 32. 最长有效括号 | 未评分 |
| 2167. 移除所有载有违禁货物车厢所需的最少时间 | 2219 |
| 2188. 完成比赛的最少时间 | 2315 |
| 2896. 执行操作使两个字符串相等 | 未评分 |
| 3389. 使字符频率相等的最少操作次数 | 2940 |
| 2597. 美丽子集的数目 | 未评分 |
§7.2 不相交区间
| 题目 | 难度分 |
|---|---|
| 2830. 销售利润最大化 | 1851 |
| 2008. 出租车的最大盈利 | 1872 |
| 2054. 两个最好的不重叠活动 | 1883 |
| 1235. 规划兼职工作 | 2023 |
| 1751. 最多可以参加的会议数目 II | 2041 |
| 3414. 不重叠区间的最大得分 | 2723 |
§7.3 subarray DP
| 题目 | 难度分 |
|---|---|
| 53. 最大子数组和 | 未评分 |
| 152. 乘积最大子数组 | 未评分 |
| 1186. 删除一次得到子数组最大和 | 1799 |
| 3738. 替换至多一个元素后最长非递减子数组 | 1811 |
| 3524. 求出数组的 X 值 I | 2008 |
| 3448. 统计可以被最后一个数位整除的子字符串数目 | 2387 |
| 2262. 字符串的总引力 | 2033 |
| 828. 统计子串中的唯一字符 | 2034 |
| 467. 环绕字符串中唯一的子字符串 | 未评分 |
§7.4 合法subsequence DP
| 题目 | 难度分 |
|---|---|
| 2501. 数组中最长的方波 | 1480 |
| 1218. 最长定差子序列 | 1597 |
| 2826. 将三个组排序 | 1721 |
| 1027. 最长等差数列 | 1759 |
| 2370. 最长理想子序列 | 1835 |
| 873. 最长的斐波那契子序列的长度 | 1911 |
| 3686. 稳定子序列的数量 | 1969 |
| 3202. 找出有效子序列的最大长度 II | 1974 |
| 446. 等差数列划分 II - 子序列 | 未评分 |
| 3351. 好子序列的元素之和 | 2086 |
| 3041. 修改数组后最大化数组中的连续元素数目 | 2231 |
| 3409. 最长相邻绝对差递减子序列 | 2500 |
| 3098. 求出所有子序列的能量和 | 2553 |
| 2901. 最长相邻不相等子序列 II | 未评分 |
| 1048. 最长字符串链 | 1599 |
| 940. 不同的子序列 II | 1985 |
| 1987. 不同的好子序列数目 | 2422 |
| 730. 统计不同回文子序列 | 未评分 |
§7.5 子矩形 DP
| 题目 | 难度分 |
|---|---|
| 3148. 矩阵中的最大得分 | 1820 |
| 221. 最大正方形 | 未评分 |
| 1277. 统计全为 1 的正方形子矩阵 | 未评分 |
| 2088. 统计农场中肥沃金字塔的数目 | 2105 |
| 3197. 包含所有 1 的最小矩形面积 II | 未评分 |
§7.6 多维 DP
| 题目 | 难度分 |
|---|---|
| 2222. 选择建筑的方案数 | 1657 |
| 2826. 将三个组排序 | 1721 |
| 2400. 恰好移动 k 步到达某一位置的方法数目 | 1751 |
| 1262. 可被三整除的最大和 | 1762 |
| 3332. 旅客可以得到的最多点数 | 1828 |
| 3176. 求出最长好子序列 I | 1849 |
| 1269. 停在原地的方案数 | 1854 |
| 3250. 单调数组对的数目 I | 1898 |
| 3218. 切蛋糕的最小总开销 I | 未评分 |
| 3122. 使矩阵满足条件的最少操作次数 | 1905 |
| 576. 出界的路径数 | 未评分 |
| 403. 青蛙过河 | 未评分 |
| 3725. 统计每一行选择互质整数的方案数 | 1982 |
| 1223. 掷骰子模拟 | 2008 |
| 1320. 二指输入的的最小距离 | 2028 |
| 3366. 最小数组和 | 2040 |
| 1575. 统计所有可行路径 | 2055 |
| 3154. 到达第 K 级台阶的方案数 | 2071 |
| 2318. 不同骰子序列的数目 | 2090 |
| 3469. 移除所有数组元素的最小代价 | 2112 |
| 2746. 字符串连接删减字母 | 2126 |
| 1444. 切披萨的方案数 | 2127 |
| 3320. 统计能获胜的出招序列数 | 2153 |
| 3429. 粉刷房子 IV | 2166 |
| 2896. 执行操作使两个字符串相等 | 2172 |
| 1420. 生成数组 | 2176 |
| 3193. 统计逆序对的数目 | 2266 |
| 1079. 活字印刷 | 未评分 |
| 1866. 恰有 K 根木棍可以看到的排列数目 | 2333 |
| 2312. 卖木头块 | 2363 |
| 3177. 求出最长好子序列 II | 2365 |
| 1884. 鸡蛋掉落-两枚鸡蛋 | 未评分 |
| 887. 鸡蛋掉落 | 2377 |
| 920. 播放列表的数量 | 2400 |
| 3336. 最大公约数相等的子序列数量 | 2403 |
| 1388. 3n 块披萨 | 2410 |
| 903. DI 序列的有效排列 | 2433 |
| 1900. 最佳运动员的比拼回合 | 2455 |
| 1531. 压缩字符串 II | 2576 |
| 1883. 准时抵达会议现场的最小跳过休息次数 | 2588 |
| 964. 表示数字的最少运算符 | 2594 |
| 3343. 统计平衡排列的数目 | 2615 |
| 1787. 使所有区间的异或结果为零 | 2640 |
| 3509. 最大化交错和为 K 的子序列乘积 | 2703 |
| 3441. 变成好标题的最少代价 | 2765 |
| 3539. 魔法序列的数组乘积之和 | 2694 |
| 2060. 同源字符串检测 | 2804 |
| 2809. 使数组和小于等于 x 的最少时间 | 2979 |
| 3003. 执行操作后的最大分割数量 | 3039 |
| 3225. 网格图操作后的最大分数 | 3028 |
八、Interval DP
§8.1 Longest Palindromic Subsequence
| 题目 | 难度分 |
|---|---|
| 516. 最长回文子序列 | 未评分 |
| 1312. 让字符串成为回文串的最少插入次数 | 1787 |
| 3472. 至多 K 次操作后的最长回文子序列 | 1884 |
| 1771. 由子序列构造的最长回文串的长度 | 2182 |
| 730. 统计不同回文子序列 | 未评分 |
§8.2 Interval DP
| 题目 | 难度分 |
|---|---|
| 5. 最长回文子串 | 未评分 |
| 647. 回文子串 | 未评分 |
| 3040. 相同分数的最大操作数目 II | 1709 |
| 375. 猜数字大小 II | 未评分 |
| 1130. 叶值的最小代价生成树 | 1919 |
| 96. 不同的二叉搜索树 | 未评分 |
| 1770. 执行乘法运算的最大分数 | 2068 |
| 1547. 切棍子的最小成本 | 2116 |
| 1039. 多边形三角剖分的最低得分 | 2130 |
| 1000. 合并石头的最低成本 | 2423 |
| 2019. 解出数学表达式的学生分数 | 2584 |
| 3563. 移除相邻字符后字典序最小的字符串 | 2585 |
| 3277. 查询子数组最大异或值 | 2693 |
| 87. 扰乱字符串 | 未评分 |
| 312. 戳气球 | 未评分 |
| 664. 奇怪的打印机 | 未评分 |
| 546. 移除盒子 | 未评分 |
九、Bitmask DP
§9.1 排列型Bitmask DP ① 相邻无关
| 题目 | 难度分 |
|---|---|
| 526. 优美的排列 | 未评分 |
| 1799. N 次操作后的最大分数和 | 未评分 |
| 3533. 判断连接可整除性 | 2257 |
| 3530. 有向无环图中合法拓扑排序的最大利润 | 2353 |
§9.2 排列型Bitmask DP ② 相邻相关
| 题目 | 难度分 |
|---|---|
| 2741. 特别的排列 | 2021 |
| 996. 平方数组的数目 | 未评分 |
| 1681. 最小不兼容性 | 2390 |
| 3615. 图中的最长回文路径 | 2463 |
| 3283. 吃掉所有兵需要的最多移动次数 | 2473 |
| 3149. 找出分数最低的排列 | 2642 |
§9.3 旅行商问题（TSP）
| 题目 | 难度分 |
|---|---|
| 943. 最短超级串 | 2186 |
§9.4 子集Bitmask DP
| 题目 | 难度分 |
|---|---|
| 2305. 公平分发饼干 | 1887 |
| 1986. 完成任务的最少工作时间段 | 1995 |
| 3670. 没有公共位的整数最大乘积 | 2234 |
| 1723. 完成所有工作的最短时间 | 2284 |
| 1655. 分配重复整数 | 2307 |
| 3444. 使数组包含目标值倍数的最少增量 | 2337 |
| 3575. 最大好子树分数 | 2360 |
| 1681. 最小不兼容性 | 2390 |
| 2572. 无平方子集计数 | 2420 |
| 1994. 好子集的数目 | 2465 |
| 1494. 并行课程 II | 未评分 |
§9.5 轮廓线 DP
| 题目 | 难度分 |
|---|---|
| 1411. 给 N x 3 网格图涂色的方案数 | 1845 |
| 1931. 用三种不同颜色为网格涂色 | 2170 |
| 1659. 最大化网格幸福感 | 2655 |
| 980. 不同路径 III | 未评分 |
§9.6 SOS DP
| 题目 | 难度分 |
|---|---|
| 3670. 没有公共位的整数最大乘积 | 2234 |
| 2044. 统计按位或能得到最大值的子集数目 | 未评分 |
| 2732. 找到矩阵中的好子集 | 未评分 |
| 3757. 有效子序列的数量 | 2519 |
§9.7 其他Bitmask DP
| 题目 | 难度分 |
|---|---|
| 473. 火柴拼正方形 | 未评分 |
| 698. 划分为k个相等的子集 | 未评分 |
| 2002. 两个回文子序列长度的最大乘积 | 1869 |
| 1125. 最小的必要团队 | 2251 |
| 1434. 每个人戴不同帽子的方案数 | 2273 |
| 464. 我能赢吗 | 未评分 |
| 691. 贴纸拼词 | 未评分 |
| 1815. 得到新鲜甜甜圈的最多组数 | 2559 |
十、Digit DP
§10.1 统计合法元素的数目
§10.2 统计合法元素的价值总和
| 题目 | 难度分 |
|---|---|
| 233. 数字 1 的个数 | 未评分 |
| 3753. 范围内总波动值 II | 2297 |
§10.3 其他Digit DP
| 题目 | 难度分 |
|---|---|
| 3677. 统计二进制回文数字的数目 | 2223 |
| 3348. 最小可整除数位乘积 II | 3101 |
十一、优化 DP
§11.1 Prefix Sum优化 DP
| 题目 | 难度分 |
|---|---|
| 1871. 跳跃游戏 VII | 1896 |
| 2327. 知道秘密的人数 | 未评分 |
| 3699. 锯齿形数组的总数 I | 2123 |
| 1997. 访问完所有房间的第一天 | 2260 |
| 629. K 个逆序对数组 | 未评分 |
| 3193. 统计逆序对的数目 | 2266 |
| 3473. 长度至少为 M 的 K 个子数组之和 | 2274 |
| 3251. 单调数组对的数目 II | 2323 |
| 2478. 完美分割的方案数 | 2344 |
| 837. 新 21 点 | 2350 |
| 3077. K 个不相交子数组的最大能量值 | 2557 |
| 3333. 找到初始输入字符串 II | 2629 |
| 2902. 和带限制的子多重集合的数目 | 2759 |
| 1977. 划分数字的方案数 | 2817 |
| 3130. 找出所有稳定的二进制数组 II | 2825 |
§11.2 Monotonic Stack优化 DP
| 题目 | 难度分 |
|---|---|
| 1335. 工作计划的最低难度 | 2035 |
| 2866. 美丽塔 II | 2072 |
| 2617. 网格图中最少访问的格子数 | 2582 |
§11.3 Monotonic Queue优化 DP
| 题目 | 难度分 |
|---|---|
| 2944. 购买水果需要的最少金币数 | 1709 |
| 1696. 跳跃游戏 VI | 1954 |
| 1425. 带限制的子序列和 | 2032 |
| 3578. 统计极差最大为 K 的分割方式数 | 2033 |
| 375. 猜数字大小 II | 未评分 |
| 1687. 从仓库到码头运输箱子 | 2610 |
| 2463. 最小移动总距离 | 未评分 |
| 2945. 找到最大非递减数组的长度 | 2943 |
§11.4 Fenwick Tree/Segment Tree优化 DP
| 题目 | 难度分 |
|---|---|
| 1626. 无矛盾的最佳球队 | 2027 |
| 2407. 最长递增子序列 II | 2280 |
| 2770. 达到末尾下标所需的最大跳跃次数 | 未评分 |
| 2926. 平衡子序列的最大和 | 2448 |
| 2547. 拆分数组的最小代价 | 未评分 |
| 3671. 子序列美丽值求和 | 2647 |
| 2916. 子数组不同元素数目的平方和 II | 2816 |
§11.5 Trie优化 DP
| 题目 | 难度分 |
|---|---|
| 139. 单词拆分 | 未评分 |
| 2707. 字符串中的额外字符 | 未评分 |
| 472. 连接词 | 2300 |
§11.6 矩阵快速幂优化 DP
| 题目 | 难度分 |
|---|---|
| 70. 爬楼梯 | 未评分 |
| 509. 斐波那契数 | 未评分 |
| 1137. 第 N 个泰波那契数 | 未评分 |
| 1220. 统计元音字母序列的数目 | 未评分 |
| 552. 学生出勤记录 II | 未评分 |
| 935. 骑士拨号器 | 未评分 |
| 790. 多米诺和托米诺平铺 | 未评分 |
| 1411. 给 N x 3 网格图涂色的方案数 | 未评分 |
| 1931. 用三种不同颜色为网格涂色 | 未评分 |
| 3337. 字符串转换后的长度 II | 2412 |
| 3700. 锯齿形数组的总数 II | 2435 |
| 2851. 字符串转换 | 2858 |
§11.7 Convex Hull Trick DP
| 题目 | 难度分 |
|---|---|
| 3494. 酿造药水需要的最少总时间 | 未评分 |
| 3500. 将数组分割为子数组的最小代价 | 未评分 |
| 3693. 爬楼梯 II | 未评分 |
§11.8 WQS 二分优化 DP
| 题目 | 难度分 |
|---|---|
| 188. 买卖股票的最佳时机 IV | 未评分 |
| 3573. 买卖股票的最佳时机 V | 未评分 |
| 2209. 用地毯覆盖后的最少白色砖块 | 未评分 |
| 3743. 循环划分的最大得分 | 未评分 |
§11.9 其他优化 DP
十二、Tree DP
§12.1 树的直径
| 题目 | 难度分 |
|---|---|
| 543. 二叉树的直径 | 未评分 |
| 687. 最长同值路径 | 未评分 |
| 124. 二叉树中的最大路径和 | 未评分 |
| 2385. 感染二叉树需要的总时间 | 1711 |
| 2246. 相邻字符不同的最长路径 | 2126 |
| 3203. 合并两棵树后的最小直径 | 2266 |
| 1617. 统计子树中城市之间最大距离 | 2309 |
| 2538. 最大价值和与最小价值和的差值 | 2398 |
| 3372. 连接两棵树后最大目标节点数目 I | 未评分 |
§12.2 树上最大独立集
| 题目 | 难度分 |
|---|---|
| 337. 打家劫舍 III | 未评分 |
| 2646. 最小化旅行的价格总和 | 2238 |
| 3544. 子树反转和 | 2545 |
§12.3 树上最小支配集
| 题目 | 难度分 |
|---|---|
| 968. 监控二叉树 | 2124 |
§12.4 Rerooting Tree DP
| 题目 | 难度分 |
|---|---|
| 834. 树中距离之和 | 2197 |
| 2581. 统计可能的树根数目 | 2228 |
| 2858. 可以到达每一个节点的最少边反转次数 | 2295 |
| 310. 最小高度树 | 未评分 |
| 3241. 标记所有节点需要的时间 | 2522 |
| 3372. 连接两棵树后最大目标节点数目 I | 未评分 |
§12.5 其他Tree DP
| 题目 | 难度分 |
|---|---|
| 2925. 在树上执行操作以后得到的最大分数 | 1940 |
| 3068. 最大节点价值之和 | 2268 |
| 2920. 收集所有金币可获得的最大积分 | 2351 |
| 3575. 最大好子树分数 | 2360 |
| 3562. 折扣价交易股票的最大利润 | 2458 |
| 1916. 统计为蚁群构筑房间的不同顺序 | 2486 |
| 3367. 移除边之后的权重最大和 | 2602 |
十三、Graph DP
十三、Graph DP
| 题目 | 难度分 |
|---|---|
| 3543. K 条边路径的最大边权和 | 2110 |
| 913. 猫和老鼠 | 2800 |
| 1728. 猫和老鼠 II | 2849 |
十四、博弈 DP
十四、博弈 DP
| 题目 | 难度分 |
|---|---|
| 1025. 除数博弈 | 1435 |
| 877. 石子游戏 | 1590 |
| 486. 预测赢家 | 未评分 |
| 1510. 石子游戏 IV | 1787 |
| 1690. 石子游戏 VII | 1951 |
| 1406. 石子游戏 III | 2027 |
| 1140. 石子游戏 II | 2035 |
| 1563. 石子游戏 V | 2087 |
| 464. 我能赢吗 | 未评分 |
| 1872. 石子游戏 VIII | 2440 |
| 913. 猫和老鼠 | 2800 |
| 1728. 猫和老鼠 II | 2849 |
十五、机率/期望 DP
十五、机率/期望 DP
| 题目 | 难度分 |
|---|---|
| 688. 骑士在棋盘上的概率 | 未评分 |
| 837. 新 21 点 | 2350 |
| 1467. 两个盒子中球的颜色数相同的概率 | 2357 |
| 808. 分汤 | 2397 |
专题：输出具体方案（打印方案）
专题：输出具体方案（打印方案）
| 题目 | 难度分 |
|---|---|
| 368. 最大整除子集 | 未评分 |
| 1363. 形成三的最大倍数 | 1823 |
| 1449. 数位成本和为目标值的最大数字 | 1927 |
| 1092. 最短公共超序列 | 1977 |
| 943. 最短超级串 | 2186 |
| 1125. 最小的必要团队 | 2251 |
| 3533. 判断连接可整除性 | 2257 |
| 3260. 找出最大的 N 位 K 回文数 | 2370 |
| 3149. 找出分数最低的排列 | 2642 |
| 3441. 变成好标题的最少代价 | 2765 |
| 3348. 最小可整除数位乘积 II | 3101 |
专题：前后缀分解
专题：前后缀分解
专题：把 X 变成 Y
专题：把 X 变成 Y
| 题目 | 难度分 |
|---|---|
| 397. 整数替换 | 未评分 |
| 2998. 使 X 和 Y 相等的最少操作次数 | 1795 |
| 2059. 转化数字的最小运算数 | 1850 |
| 991. 坏了的计算器 | 1909 |
| 1553. 吃掉 N 个橘子的最少天数 | 2048 |
专题：跳跃游戏
专题：跳跃游戏
| 题目 | 难度分 |
|---|---|
| 2770. 达到末尾下标所需的最大跳跃次数 | 1533 |
| 403. 青蛙过河 | 未评分 |
| 1340. 跳跃游戏 V | 1866 |
| 1871. 跳跃游戏 VII | 1896 |
| 1696. 跳跃游戏 VI | 1954 |
| 975. 奇偶跳 | 2079 |
| 1654. 到家的最少跳跃次数 | 2124 |
其他
杂项
| 题目 | 难度分 |
|---|---|
| 1387. 将整数按权重排序 | 1507 |
| 823. 带因子的二叉树 | 1900 |
| 756. 金字塔转换矩阵 | 1990 |
| 2930. 重新排列后包含指定子字符串的字符串数目 | 2227 |
| 1896. 反转表达式值的最少操作次数 | 2532 |
这是阶段二的第三份题单；多重背包与树上背包两个小节标为选做，留在进阶题单里，路线会继续沿着核心章节往前走。
难度分来自 zerotrac 的 LeetCode 竞赛评分。部分题目没有 zerotrac 分数，会标记为“未评分”。
进入书房