动态规划 力扣专题

入门DP

爬楼梯

• 2266. 统计打字方案数

• 2466. 统计构造好字符串的方案数

• 377. 组合总和 Ⅳ

  额外难点：必刷题！DP计算排列而非组合的设计思路

• 3693. 爬楼梯 II

• 746. 使用最小花费爬楼梯

• 70. 爬楼梯

打家劫舍

• 198. 打家劫舍

• 213. 打家劫舍 II

  额外难点：环形DP处理

• 2320. 统计放置房子的方式数

• 3186. 施咒的最大总伤害

  额外难点：必刷题！对称值域的处理

• 2140. 解决智力问题

• 740. 删除并获得点数

  额外难点：同3186，必刷题！对称值域的处理

最大子数组和（最大子段和）

• 53. 最大子数组和

• 1186. 删除一次得到子数组最大和

• 152. 乘积最大子数组

• 2321. 拼接数组的最大分数

  额外难点：最大子数组和的必刷题！通过数学优化后，抽象为DP

• 918. 环形子数组的最大和

  额外难点：最大子数组和的必刷题！对于限制长度的最大子数组和的处理

• 1191. K 次串联后最大子数组之和

  额外难点：最大子数组和的必刷题！对于不限制长度的最大子数组和的处理

• 1749. 任意子数组和的绝对值的最大值

  额外难点：最大子数组和的必刷题！求绝对值转换为求最大子数组和

• 2606. 找到最大开销的子字符串

背包(选还是不选)

01背包(只能选一次)

• 474. 一和零

  额外难点：01背包的精髓题，只刷这一题就够了

• 3181. 执行操作可获得的最大总奖励 II

  额外难点：位运算、贪心

• 2742. 给墙壁刷油漆

  额外难点：贪心、后效性判定

• 2518. 好分区的数目

• 3287. 求出数组中最大序列值

  额外难点：前后缀的设计

• 956. 最高的广告牌

  额外难点：差值DP、滚动数组

• 3082. 求出所有子序列的能量和

  额外难点：计数DP、滚动数组

• 879. 盈利计划

  额外难点：01背包的精髓题

• 1049. 最后一块石头的重量 II

• 3489. 零数组变换 IV

  额外难点：01背包、多重背包、二分的综合题

• 416. 分割等和子集

• 3685. 含上限元素的子序列和

  额外难点：01背包、双指针的综合题

• 3180. 执行操作可获得的最大总奖励 I

• 2787. 将一个数字表示成幂的和的方案数

• 2915. 和为目标值的最长子序列的长度

• 494. 目标和

  额外难点：01背包、数学优化、乘法原理

• LCP 47. 入场安检

  额外难点：栈、队列与01背包的综合题

完全背包（选无数次）

• 1449. 数位成本和为目标值的最大数字

  额外难点：精髓题，必刷！

• 322. 零钱兑换

• 279. 完全平方数

• 518. 零钱兑换 II

• 3592. 硬币面值还原

多重背包(可以选多次)

• 1774. 最接近目标价格的甜点成本

• 2585. 获得分数的方法数

  额外难点：多重背包的精髓题，前缀和、滑动窗口优化

• 3333. 找到初始输入字符串 II

  额外难点：逆事件的乘法原理优化

• 2902. 和带限制的子多重集合的数目

  额外难点：乘法原理、前缀和、滑动窗口优化

分组背包(每个组选一个或者不选)

• 2218. 从栈中取出 K 个硬币的最大面值和

  额外难点：前缀和

• 1981. 最小化目标值与所选元素的差

  额外难点：贪心

• 1155. 掷骰子等于目标和的方法数

经典线性DP

最长公共子序列 LCS

基础

• 72. 编辑距离

• 1143. 最长公共子序列

  额外难点：最优性剪枝

• 1458. 两个子序列的最大点积

• 718. 最长重复子数组

• 583. 两个字符串的删除操作

• 712. 两个字符串的最小ASCII删除和

• 1035. 不相交的线

  额外难点：最优性剪枝

进阶

• 3628. 插入一个字母的最大子序列数

  额外难点：前后缀分解

• 10. 正则表达式匹配

  额外难点：LCS的必刷题！初始值、状态设计

• 44. 通配符匹配

  额外难点：LCS的必刷题！初始值、状态设计

• 3290. 最高乘法得分

• 97. 交错字符串

• 1639. 通过给定词典构造目标字符串的方案数

• 115. 不同的子序列

• 1092. 最短公共超序列

  额外难点：LCS的必刷题，必刷题！是SCS的模板题

• 3316. 从原字符串里进行删除操作的最多次数

  额外难点：初始值、状态设计

最长递增子序列LIS

基础

• 300. 最长递增子序列

• 2826. 将三个组排序

  额外难点：最长单调不减序列的编程，是“单调不减”，不是普通的“单调递增”

• 2111. 使数组 K 递增的最少操作次数

  额外难点：转换为最长单调不减序列的问题建模

• 1964. 找出到每个位置为止最长的有效障碍赛跑路线

  额外难点：同样还是转换为最长单调不减序列问题

• 1671. 得到山形数组的最少删除次数

  额外难点：前后缀分解

进阶

• 2407. 最长递增子序列 II

  额外难点：线段树

• 673. 最长递增子序列的个数

  额外难点：LIS的必刷题！二分、前缀和、贪心

• 368. 最大整除子集

  额外难点：整除的链式传递性质，必刷！

• 354. 俄罗斯套娃信封问题

  额外难点：排序优化单调性

• 960. 删列造序 III

  额外难点：状态设计

• 1187. 使数组严格递增

  额外难点：LIS的必刷题！LIS删除与改变元素的区别、构造、贪心

• 1713. 得到子序列的最少操作次数

  额外难点：特殊条件下，LCS转换为LIS

• 2901. 最长相邻不相等子序列 II

• 1626. 无矛盾的最佳球队

• 1691. 堆叠长方体的最大高度

  额外难点：LIS的必刷题！多维排序时找规律

划分DP(将数组拆分为相邻或相间的连续子数组)

划分可行性

• 2369. 检查数组是否存在有效划分

• 139. 单词拆分

  额外难点：字典树

没有个数限制

• 132. 分割回文串 II

  额外难点：回文串

• 2707. 字符串中的额外字符

  额外难点：回文串

• 3196. 最大化子数组的总成本

  额外难点：数学、滚动数组

• 2767. 将字符串分割为最少的美丽子字符串

• 91. 解码方法

  额外难点：滚动数组

• 639. 解码方法 II

• LCR 165. 解密数字

  额外难点：滚动数组

• 1043. 分隔数组以得到最大和

• 1416. 恢复数组

• 2472. 不重叠回文子字符串的最大数目

  额外难点：贪心、manacher、回文串

• 3578. 统计极差最大为 K 的分割方式数

  额外难点：单调队列、前缀和

• 3144. 分割字符频率相等的最少子字符串

• 1105. 填充书架

• 2547. 拆分数组的最小代价

• 2430. 对字母串可执行的最大删除数

  额外难点：LCP

• 3579. 字符串转换需要的最小操作数

  额外难点：中心扩展、回文串、贪心、哈希表

• 2463. 最小移动总距离

  额外难点：贪心

• 3500. 将数组分割为子数组的最小代价

  额外难点：后缀和、数学

有个数限制

• 813. 最大平均值和的分组

• 3599. 划分数组得到最小 XOR

  额外难点：二分、异或前缀

• 410. 分割数组的最大值

  额外难点：贪心、二分

• 1278. 分割回文串 III

  额外难点：回文串

• 1745. 分割回文串 IV

  额外难点：回文串

• 1335. 工作计划的最低难度

  额外难点：单调栈

• 1478. 安排邮筒

  额外难点：中位数、数学、前缀和

• 2209. 用地毯覆盖后的最少白色砖块

  额外难点：区间重叠

• 1473. 粉刷房子 III

  额外难点：逻辑上的划分，初始值设定

• 3473. 长度至少为 M 的 K 个子数组之和

  额外难点：数学、区间长度限制下的剪枝

• 2478. 完美分割的方案数

  额外难点：双指针、区间长度限制下的剪枝

• 1959. K 次调整数组大小浪费的最小总空间

状态机DP

买卖股票

• 121. 买卖股票的最佳时机

• 122. 买卖股票的最佳时机 II

• 123. 买卖股票的最佳时机 III

  额外难点：滚动数组

• 188. 买卖股票的最佳时机 IV

  额外难点：滚动数组

• 3573. 买卖股票的最佳时机 V

  额外难点：状态设计、初始值

• 714. 买卖股票的最佳时机含手续费

• 309. 买卖股票的最佳时机含冷冻期

基础

• 3259. 超级饮料的最大强化能量

• 2708. 一个小组的最大实力值

  额外难点：初始值、状态设计、数学

• 1567. 乘积为正数的最长子数组长度

  额外难点：初始值、状态设计、数学

• 1911. 最大交替子序列和

  额外难点：状态设计

• 2786. 访问数组中的位置使分数最大

  额外难点：初始值、状态设计

• 376. 摆动序列

  额外难点：贪心

• 2222. 选择建筑的方案数

  额外难点：状态压缩

进阶

• 2919. 使数组变美的最小增量运算数

  额外难点：状态设计

• 1537. 最大得分

  额外难点：双指针、状态设计

• 3738. 替换至多一个元素后最长非递减子数组

  额外难点：创新的状态设计！

• 1186. 删除一次得到子数组最大和

  额外难点：创新的状态设计！

• 2771. 构造最长非递减子数组

• 3628. 插入一个字母的最大子序列数

  额外难点：前后缀分解

• 1594. 矩阵的最大非负积

• 935. 骑士拨号器

• 3640. 三段式数组 II

  额外难点：前后缀分解、状态设计

• 3068. 最大节点价值之和

  额外难点：问题建模、状态设计、贪心

• 3434. 子数组操作后的最大频率

  额外难点：高难度的滚动数组，要好好学；状态设计、贪心

• 801. 使序列递增的最小交换次数

• 1955. 统计特殊子序列的数目

其他线性DP

一维DP

• 2140. 解决智力问题

• 368. 最大整除子集

  额外难点：必刷题！整除的链式传递性质

• 2901. 最长相邻不相等子序列 II

• 3147. 从魔法师身上吸取的最大能量

  额外难点：结尾选择

• 2944. 购买水果需要的最少金币数

  额外难点：必刷题！逆序考虑状态转移方程！

• 650. 两个键的键盘

• 983. 最低票价

  额外难点：必刷必刷题！向前覆盖问题的逆序、正序设计，以及双指针单调性优化

• 2597. 美丽子集的数目

  额外难点：必刷题！同余分组+排列组合+打家劫舍！

• 32. 最长有效括号

  额外难点：栈的括号匹配问题用DP解

• 871. 最低加油次数

  额外难点：问题抽象的建模转换

• 2896. 执行操作使两个字符串相等

  额外难点：必刷题！从一个字符串转换为另一个字符串的新思路！

• 2167. 移除所有载有违禁货物车厢所需的最少时间

  额外难点：前后缀分解+状态机DP的好题

• 2188. 完成比赛的最少时间

  额外难点：用贪心进行初始化打表

不相交区间

• 2830. 销售利润最大化

• 2008. 出租车的最大盈利

• 2054. 两个最好的不重叠活动

  额外难点：时间戳

• 1235. 规划兼职工作

• 1751. 最多可以参加的会议数目 II

子数组DP

• 467. 环绕字符串中唯一的子字符串

  额外难点：无穷循环DP的处理

• 2262. 字符串的总引力

  额外难点：子数组之间的状态转移

• 3524. 求出数组的 X 值 I

  额外难点：子数组之间的状态转移、乘法取模

• 828. 统计子串中的唯一字符

  额外难点：子数组之间的状态转移、乘法取模

• 53. 最大子数组和

• 152. 乘积最大子数组

• 3738. 替换至多一个元素后最长非递减子数组

  额外难点：发掘前后缀分解的规律

• 1186. 删除一次得到子数组最大和

  额外难点：发掘前后缀分解的规律

合法子序列 DP(f[x]以元素值x结尾的合法子序列，而非下标；如果x不是整数，或者值域范围很大，可以用哈希表代替数组)

• 2901. 最长相邻不相等子序列 II

• 2826. 将三个组排序

• 730. 统计不同回文子序列

  额外难点：必刷题！回文子序列的经典题！

• 2501. 数组中最长的方波

• 1218. 最长定差子序列

• 1027. 最长等差数列

• 2370. 最长理想子序列

• 873. 最长的斐波那契子序列的长度

  额外难点：必刷题！按值DP的易错点！

• 3686. 稳定子序列的数量

  额外难点：状态机DP的视角处理子序列

• 3202. 找出有效子序列的最大长度 II

  额外难点：必刷题！必刷题！按值DP的经典题！

• 1048. 最长字符串链

• 446. 等差数列划分 II - 子序列

  额外难点：状态的设计

• 940. 不同的子序列 II

  额外难点：必刷题！必刷题！序列去重的经典题！

• 3351. 好子序列的元素之和

  额外难点：计算状态的贡献

• 3041. 修改数组后最大化数组中的连续元素数目

子矩形 DP

• 221. 最大正方形
• 1277. 统计全为 1 的正方形子矩阵
• 3148. 矩阵中的最大得分
• 2088. 统计农场中肥沃金字塔的数目

区间DP

最长回文子序列

• 516. 最长回文子序列

• 730. 统计不同回文子序列

  额外难点：必刷题！回文子序列的经典题！

• 1312. 让字符串成为回文串的最少插入次数

  额外难点：转换为回文子序列

• 3472. 至多 K 次操作后的最长回文子序列

• 1771. 由子序列构造的最长回文串的长度

区间 DP

• 96. 不同的二叉搜索树

• 375. 猜数字大小 II

• 647. 回文子串

  额外难点：必刷题！三种方法求回文串

• 5. 最长回文子串

• 664. 奇怪的打印机

  额外难点：必刷题！区间DP模板题

• 312. 戳气球

  额外难点：必刷题！消消乐上下文无关的模板题

• 546. 移除盒子

  额外难点：必刷题！消消乐上下文有关的模板题

• 87. 扰乱字符串

  额外难点：两个字符串时的区间DP

• 3040. 相同分数的最大操作数目 II

• 1770. 执行乘法运算的最大分数

  额外难点：自行构造区间DP的状态设计

• 1547. 切棍子的最小成本

  额外难点：自行构造区间DP的状态设计

• 1039. 多边形三角剖分的最低得分

  额外难点：自行构造区间DP的状态设计

• 1130. 叶值的最小代价生成树

计数DP

• 装饰围栏

  额外难点：试填法