03. 线性 DP 题目
03. 线性 DP 题目
线性 DP 题目
单串线性 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 | 整数拆分 | - | 数学、动态规划 | 中等 |
来源：https://github.com/itcharge/LeetCode-Py