跳至主要內容

03. 线性 DP 题目

ITCharge大约 7 分钟

线性 DP 题目

单串线性 DP 问题

题号标题题解标签难度
0300最长递增子序列open in new windowPythonopen in new window数组、二分查找、动态规划中等
0673最长递增子序列的个数open in new windowPythonopen in new window树状数组、线段树、数组、动态规划中等
0354俄罗斯套娃信封问题open in new windowPythonopen in new window数组、二分查找、动态规划、排序困难
0053最大子数组和open in new windowPythonopen in new window数组、分治、动态规划中等
0152乘积最大子数组open in new windowPythonopen in new window数组、动态规划中等
0918环形子数组的最大和open in new windowPythonopen in new window队列、数组、分治、动态规划、单调队列中等
0198打家劫舍open in new windowPythonopen in new window数组、动态规划中等
0213打家劫舍 IIopen in new windowPythonopen in new window数组、动态规划中等
0740删除并获得点数open in new window数组、哈希表、动态规划中等
13883n 块披萨open in new window贪心、数组、动态规划、堆(优先队列)困难
0873最长的斐波那契子序列的长度open in new windowPythonopen in new window数组、哈希表、动态规划中等
1027最长等差数列open in new window数组、哈希表、二分查找、动态规划中等
1055形成字符串的最短路径open in new window贪心、双指针、字符串中等
0368最大整除子集open in new window数组、数学、动态规划、排序中等
0032最长有效括号open in new windowPythonopen in new window栈、字符串、动态规划困难
0413等差数列划分open in new window数组、动态规划中等
0091解码方法open in new windowPythonopen in new window字符串、动态规划中等
0639解码方法 IIopen in new windowPythonopen in new window字符串、动态规划困难
0132分割回文串 IIopen in new window字符串、动态规划困难
1220统计元音字母序列的数目open in new windowPythonopen in new window动态规划困难
0338比特位计数open in new windowPythonopen in new window位运算、动态规划简单
0801使序列递增的最小交换次数open in new windowPythonopen in new window数组、动态规划困难
0871最低加油次数open in new window贪心、数组、动态规划、堆(优先队列)困难
0045跳跃游戏 IIopen in new windowPythonopen in new window贪心、数组、动态规划中等
0813最大平均值和的分组open in new window数组、动态规划、前缀和中等
0887鸡蛋掉落open in new windowPythonopen in new window数学、二分查找、动态规划困难
0256粉刷房子open in new window数组、动态规划中等
0265粉刷房子 IIopen in new window数组、动态规划困难
1473粉刷房子 IIIopen in new window数组、动态规划困难
0975奇偶跳open in new window栈、数组、动态规划、有序集合、单调栈困难
0403青蛙过河open in new windowPythonopen in new window数组、动态规划困难
1478安排邮筒open in new window数组、数学、动态规划、排序困难
1230抛掷硬币open in new window数学、动态规划、概率与统计中等
0410分割数组的最大值open in new windowPythonopen in new window贪心、数组、二分查找、动态规划、前缀和困难
1751最多可以参加的会议数目 IIopen in new window数组、二分查找、动态规划、排序困难
1787使所有区间的异或结果为零open in new window位运算、数组、动态规划困难
0121买卖股票的最佳时机open in new windowPythonopen in new window数组、动态规划简单
0122买卖股票的最佳时机 IIopen in new windowPythonopen in new window贪心、数组中等
0123买卖股票的最佳时机 IIIopen in new windowPythonopen in new window数组、动态规划困难
0188买卖股票的最佳时机 IVopen in new windowPythonopen in new window数组、动态规划困难
0309最佳买卖股票时机含冷冻期open in new windowPythonopen in new window数组、动态规划中等
0714买卖股票的最佳时机含手续费open in new windowPythonopen in new window贪心、数组中等

双串线性 DP 问题

题号标题题解标签难度
1143最长公共子序列open in new windowPythonopen in new window字符串、动态规划中等
0712两个字符串的最小ASCII删除和open in new window字符串、动态规划中等
0718最长重复子数组open in new windowPythonopen in new window数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希中等
0583两个字符串的删除操作open in new windowPythonopen in new window字符串、动态规划中等
0072编辑距离open in new windowPythonopen in new window字符串、动态规划困难
0044通配符匹配open in new windowPythonopen in new window贪心、递归、字符串、动态规划困难
0010正则表达式匹配open in new windowPythonopen in new window递归、字符串、动态规划困难
0097交错字符串open in new window字符串、动态规划中等
0115不同的子序列open in new windowPythonopen in new window字符串、动态规划困难
0087扰乱字符串open in new window字符串、动态规划困难

矩阵线性 DP 问题

题号标题题解标签难度
0118杨辉三角open in new windowPythonopen in new window数组、动态规划简单
0119杨辉三角 IIopen in new windowPythonopen in new window数组、动态规划简单
0120三角形最小路径和open in new windowPythonopen in new window数组、动态规划中等
0064最小路径和open in new windowPythonopen in new window数组、动态规划、矩阵中等
0174地下城游戏open in new window数组、动态规划、矩阵困难
0221最大正方形open in new windowPythonopen in new window数组、动态规划、矩阵中等
0931下降路径最小和open in new window数组、动态规划、矩阵中等
0576出界的路径数open in new windowPythonopen in new window动态规划中等
0085最大矩形open in new window栈、数组、动态规划、矩阵、单调栈困难
0363矩形区域不超过 K 的最大数值和open in new window数组、二分查找、矩阵、有序集合、前缀和困难
面试题 17.24最大子矩阵open in new window数组、动态规划、矩阵、前缀和困难
1444切披萨的方案数open in new window记忆化搜索、数组、动态规划、矩阵困难

无串线性 DP 问题

题号标题题解标签难度
1137第 N 个泰波那契数open in new windowPythonopen in new window记忆化搜索、数学、动态规划简单
0650只有两个键的键盘open in new windowPythonopen in new window数学、动态规划中等
0264丑数 IIopen in new windowPythonopen in new window哈希表、数学、动态规划、堆(优先队列)中等
0279完全平方数open in new windowPythonopen in new window广度优先搜索、数学、动态规划中等
0343整数拆分open in new windowPythonopen in new window数学、动态规划中等