潍坊网站建设选聚搜网络好,软件商店电脑版下载,附近设计公司,微信商城是什么文章目录一、 动态规划基础知识1.1 动态规划简介1.2 动态规划的特征1.2.1 最优子结构性质1.2.2 重叠子问题性质1.2.3 无后效性1.3 动态规划的基本思路1.4 动态规划基础应用1.4.1 斐波那契数1.4.2 爬楼梯1.4.3 不同路径1.5 个人总结二、记忆化搜索2.1 记忆化搜索简介2.2 记忆化搜…
文章目录一、 动态规划基础知识1.1 动态规划简介1.2 动态规划的特征1.2.1 最优子结构性质1.2.2 重叠子问题性质1.2.3 无后效性1.3 动态规划的基本思路1.4 动态规划基础应用1.4.1 斐波那契数1.4.2 爬楼梯1.4.3 不同路径1.5 个人总结二、记忆化搜索2.1 记忆化搜索简介2.2 记忆化搜索与递推的区别2.3 记忆化搜索的应用2.3.1 目标和2.3.2 第 N 个泰波那契数三、线性动态规划简介3.1 单串线性 DP 问题3.1.1 最长递增子序列3.1.2 最大子数组和3.1.2.1 动态规划3.1.2.2 动态规划滚动数组3.1.3 最长的斐波那契子序列的长度3.1.3.1 暴力枚举超时3.1.3.2 哈希表3.1.3.3 动态规划 哈希表3.2 双串线性 DP 问题3.2.1 最长公共子序列3.2.2 最长重复子数组3.3.3 编辑距离3.3 矩阵线性 DP问题3.3.1 最小路径和3.3.2最大正方形3.4无串线性 DP 问题3.4.1 整数拆分3.4.2 只有两个键的键盘3.5 线性 DP 题目大全参考《OI Wiki动态规划》、《算法通关手册》动态规划篇 一、 动态规划基础知识
1.1 动态规划简介 动态规划Dynamic Programming简称 DP是一种通过把原问题分解为相对简单的子问题的方式而求解复杂问题的方法。
动态规划方法与分治算法类似却又不同于分治算法。
「动态规划的核心思想」是
把「原问题」分解为「若干个重叠的子问题」每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后动态规划方法才会执行下一个阶段的计算。在求解子问题的过程中按照自底向上的顺序求解出「子问题的解」把结果存储在表格中当需要再次求解此子问题时直接从表格中查询该子问题的解从而避免了大量的重复计算。 「动态规划方法与分治算法的不同点」在于
适用于动态规划求解的问题在分解之后得到的子问题往往是相互联系的会出现若干个重叠子问题。使用动态规划方法会将这些重叠子问题的解保存到表格里供随后的计算查询使用从而避免大量的重复计算。
1.2 动态规划的特征 能够使用动态规划方法解决的问题必须满足下面三个特征「最优子结构性质」、「重叠子问题性质」和「无后效性」。
1.2.1 最优子结构性质
「最优子结构」指的是一个问题的最优解包含其子问题的最优解。 举个例子如下图所示原问题 S{a1,a2,a3,a4}S \lbrace a_1, a_2, a_3, a_4 \rbraceS{a1,a2,a3,a4}在 a1a_1a1 步我们选出一个当前最优解之后问题就转换为求解子问题 S子问题{a2,a3,a4}S_{子问题} \lbrace a_2, a_3, a_4 \rbraceS子问题{a2,a3,a4}。如果原问题 SSS 的最优解可以由「第 a1a_1a1 步得到的局部最优解」和「 S子问题S_{子问题}S子问题 的最优解」构成则说明该问题满足最优子结构性质。
也就是说如果原问题的最优解包含子问题的最优解则说明该问题满足最优子结构性质。 1.2.2 重叠子问题性质 「重叠子问题性质」指的是在求解子问题的过程中有大量的子问题是重复的一个子问题会在下一阶段的决策中可能会被多次用到。如果有大量重复的子问题那么只需要对求解一次然后用表格将结果存储下来以后使用时可以直接查询不需要再次求解。 举个例子比如斐波那契数列的定义是f(1) 1, f(2) 2, f(n) f(n - 1) f(n - 2)。对应的递推过程如下图所示其中 f(1)、f(2)、f(3)、f(4) 都进行了多次重复计算。而如果我们在第一次计算 f(1)、f(2)、f(3)、f(4) 时就将其结果存入表格则再次使用时可以直接查询从而避免重复求解相同的子问题提升效率。 1.2.3 无后效性 「无后效性」指的是子问题的解状态值只与之前阶段有关而与后面阶段无关。当前阶段的若干状态值一旦确定就不再改变不会再受到后续阶段决策的影响。换句话说一旦某一个子问题的求解结果确定以后就不会再被修改。 其实我们也可以把动态规划方法的求解过程看做是有向无环图的最长最短路的求解过程。每个状态对应有向无环图上的一个节点决策对应图中的一条有向边。 如果一个问题具有「后效性」则可能需要将其转化或者逆向求解来消除后效性然后才可以使用动态规划方法。
1.3 动态规划的基本思路 如下图所示我们在使用动态规划方法解决某些最优化问题时可以将解决问题的过程按照一定顺序时间顺序、空间顺序或其他顺序分解为若干个相互联系的「阶段」。然后按照顺序对每一个阶段做出「决策」这个决策既决定了本阶段的效益也决定了下一阶段的初始状态。依次做完每个阶段的决策之后就得到了一个整个问题的决策序列。 这样就将一个原问题分解为了一系列的子问题然后通过逐步求解从而获得最终结果。 这种前后关联、具有链状结构的多阶段进行决策的问题也叫做「多阶段决策问题」。通常我们使用动态规划方法来解决多阶段决策问题其基本思路如下
划分阶段将原问题按顺序时间顺序、空间顺序或其他顺序分解为若干个相互联系的「阶段」。划分后的阶段⼀定是有序或可排序的否则问题⽆法求解。 这里的「阶段」指的是⼦问题的求解过程。每个⼦问题的求解过程都构成⼀个「阶段」在完成前⼀阶段的求解后才会进⾏后⼀阶段的求解。 定义状态将和子问题相关的某些变量位置、数量、体积、空间等等作为一个「状态」表示出来。状态的选择要满⾜⽆后效性。 一个「状态」对应一个或多个子问题所谓某个「状态」下的值指的就是这个「状态」所对应的子问题的解。 状态转移根据「上一阶段的状态」和「该状态下所能做出的决策」推导出「下一阶段的状态」。或者说根据相邻两个阶段各个状态之间的关系确定决策然后推导出状态间的相互转移方式即「状态转移方程」。初始条件和边界条件根据问题描述、状态定义和状态转移方程确定初始条件和边界条件。最终结果确定问题的求解目标然后按照一定顺序求解每一个阶段的问题。最后根据状态转移方程的递推结果确定最终结果。
1.4 动态规划基础应用 动态规划相关的问题往往灵活多变思维难度大没有特别明显的套路并且经常会在各类算法竞赛和面试中出现。 动态规划问题的关键点在于「如何状态设计」和「推导状态转移条件」还有各种各样的「优化方法」。这类问题一定要多练习、多总结只有接触的题型多了才能熟练掌握动态规划思想。 下面来介绍几道关于动态规划的基础题目。
题号标题题解标签难度0509斐波那契数Python数组简单0070爬楼梯Python动态规划简单0062不同路径Python数组、动态规划中等
1.4.1 斐波那契数 509. 斐波那契数 - 力扣 给定一个整数 n。计算第 n 个斐波那契数。其中斐波那契数列的定义如下
f(0) 0, f(1) 1。f(n) f(n - 1) f(n - 2)其中 n 1。
解题思路 划分阶段按照整数顺序进行阶段划分将其划分为整数 0 ~ n。 定义状态定义状态 dp[i] 为第 i 个斐波那契数。 状态转移方程 根据题目中所给的斐波那契数列的定义 f(n) f(n - 1) f(n - 2)则直接得出状态转移方程为 dp[i] dp[i - 1] dp[i - 2]。 初始条件 根据题目中所给的初始条件 f(0) 0, f(1) 1 确定动态规划的初始条件即 dp[0] 0, dp[1] 1。 最终结果 根据状态定义最终结果为 dp[n]即第 n 个斐波那契数为 dp[n]。
class Solution:def fib(self, n: int) - int:if n 1:return ndp [0 for _ in range(n 1)]dp[0] 0dp[1] 1for i in range(2, n 1):dp[i] dp[i - 2] dp[i - 1]return dp[n]复杂度分析
时间复杂度O(n)O(n)O(n)。一重循环遍历的时间复杂度为 O(n)O(n)O(n)。空间复杂度O(n)O(n)O(n)。 用到了一维数组保存状态所以总体空间复杂度为 O(n)O(n)O(n)。因为 dp[i] 的状态只依赖于 dp[i - 1] 和 dp[i - 2]所以可以使用 3 个变量来分别表示 dp[i]、dp[i - 1]、dp[i - 2]从而将空间复杂度优化到 O(1)O(1)O(1)。
1.4.2 爬楼梯 70. 爬楼梯 - 力扣 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。现在给定一个整数 n。请计算出有多少种不同的方法可以爬到楼顶。
1≤n≤451 \le n \le 451≤n≤45。
示例
输入 n 3
输出 3
解释 有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶解题思路 划分阶段 我们按照台阶的阶层划分阶段将其划分为 0 ~ n 阶。 定义状态 定义状态 dp[i] 为爬到第 i 阶台阶的方案数。 状态转移方程 根据题目大意每次只能爬 1 或 2 个台阶。则第 i 阶楼梯只能从第 i - 1 阶向上爬 1阶上来或者从第 i - 2 阶向上爬 2 阶上来。所以可以推出状态转移方程为 dp[i] dp[i - 1] dp[i - 2]。 初始条件 第 0 层台阶方案数可以看做 1 种方法从 0 阶向上爬 0 阶即 dp[1] 1。第 1 层台阶方案数1 种方法从 0 阶向上爬 1 阶即 dp[1] 1。第 2 层台阶方案数2 中方法从 0 阶向上爬 2 阶或者从 1 阶向上爬 1 阶。 最终结果 根据状态定义最终结果为 dp[n]即爬到第 n 阶台阶即楼顶的方案数为 dp[n]。 虽然这道题跟上一道题的状态转移方程都是 dp[i] dp[i - 1] dp[i - 2]但是两道题的考察方式并不相同一定程度上也可以看出来动态规划相关题目的灵活多变。
代码
class Solution:def climbStairs(self, n: int) - int:dp [0 for _ in range(n 1)]dp[0] 1dp[1] 1for i in range(2, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[n]复杂度分析
时间复杂度O(n)O(n)O(n)。一重循环遍历的时间复杂度为 O(n)O(n)O(n)。空间复杂度O(n)O(n)O(n)。 用到了一维数组保存状态所以总体空间复杂度为 O(n)O(n)O(n)。因为 dp[i] 的状态只依赖于 dp[i - 1] 和 dp[i - 2]所以可以使用 3 个变量来分别表示 dp[i]、dp[i - 1]、dp[i - 2]从而将空间复杂度优化到 O(1)O(1)O(1)。
1.4.3 不同路径 62. 不同路径 - 力扣 给定两个整数 m 和 n代表大小为 m * n 的棋盘 一个机器人位于棋盘左上角的位置机器人每次只能向右、或者向下移动一步。要求计算出机器人从棋盘左上角到达棋盘右下角一共有多少条不同的路径。
1≤m,n≤1001 \le m, n \le 1001≤m,n≤100。题目数据保证答案小于等于 2∗1092 * 10^92∗109。
示例
输入 m 3, n 7
输出 28解题思路 划分阶段 按照路径的结尾位置行位置、列位置组成的二维坐标进行阶段划分。 定义状态 定义状态 dp[i][j] 为从左上角到达 (i, j) 位置的路径数量。 状态转移方程 因为我们每次只能向右、或者向下移动一步因此想要走到 (i, j)只能从 (i - 1, j) 向下走一步走过来或者从 (i, j - 1) 向右走一步走过来。所以可以写出状态转移方程为dp[i][j] dp[i - 1][j] dp[i][j - 1]此时 i 0j 0。 初始条件 从左上角走到 (0, 0) 只有一种方法即 dp[0][0] 1。第一行元素只有一条路径即只能通过前一个元素向右走得到所以 dp[0][j] 1。同理第一列元素只有一条路径即只能通过前一个元素向下走得到所以 dp[i][0] 1。 最终结果 根据状态定义最终结果为 dp[m - 1][n - 1]即从左上角到达右下角 (m - 1, n - 1) 位置的路径数量为 dp[m - 1][n - 1]。
代码
class Solution(object):def uniquePaths(self, m, n)::type m: int:type n: int:rtype: int# 使用一个二维列表进行存储dp[i][j]表示i行j列有多少种路径dp[[0]*n for _ in range(m)]for i in range(m):dp[i][0]1 # 第一列路径为1for j in range(n):dp[0][j]1 # 第一行路径为1if i0 and j0: # 第一行第一列之外的位置路径数为上方位置和左边位置的路径数之和dp[i][j]dp[i-1][j]dp[i][j-1]return dp[m-1][n-1]复杂度分析
时间复杂度O(m∗n)O(m * n)O(m∗n)。初始条件赋值的时间复杂度为 O(mn)O(m n)O(mn)两重循环遍历的时间复杂度为 O(m∗n)O(m * n)O(m∗n)所以总体时间复杂度为 O(m∗n)O(m * n)O(m∗n)。空间复杂度 O(m∗n)O(m * n)O(m∗n)。用到了二维数组保存状态所以总体空间复杂度为 O(m∗n)O(m * n)O(m∗n)。因为 dp[i][j] 的状态只依赖于上方值 dp[i - 1][j] 和左侧值 dp[i][j - 1]而我们在进行遍历时的顺序刚好是从上至下、从左到右。所以我们可以使用长度为 m 的一维数组来保存状态从而将空间复杂度优化到 O(m)O(m)O(m)。
1.5 个人总结 枚举算法Enumeration Algorithm即穷举法指的是按照问题本身的性质一一列举出该问题所有可能的解并在逐一列举的过程中将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中既不能遗漏也不能重复。 分治算法Divide and Conquer「分而治之」把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。 递归Recursion通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中可以通过在函数中再次调用函数自身的方式来实现递归。 动态规划Dynamic Programming 类似分治将复杂问题分解为更简单的子问题进行求解划分阶段类似枚举会计算出每个阶段的结果子问题最优解但是下一阶段的结果是根据上一阶段的结果算出而不是直接从头计算所以存在状态转移提高效率重复调用根据上一阶段的结果来计算下一阶段的结果所以使用动态规划方法会将各阶段的解保存到表格里供随后的计算查询使用从而避免大量的重复计算。
二、记忆化搜索
2.1 记忆化搜索简介 记忆化搜索Memoization Search是一种通过存储已经遍历过的状态信息从而避免对同一状态重复遍历的搜索算法。 记忆化搜索是动态规划的一种实现方式。在记忆化搜索中当算法需要计算某个子问题的结果时它首先检查是否已经计算过该问题。如果已经计算过则直接返回已经存储的结果否则计算该问题并将结果存储下来以备将来使用。 举个例子比如「斐波那契数列」的定义是f(0)0,f(1)1,f(n)f(n−1)f(n−2)f(0) 0, f(1) 1, f(n) f(n - 1) f(n - 2)f(0)0,f(1)1,f(n)f(n−1)f(n−2)。如果我们使用递归算法求解第 nnn 个斐波那契数则对应的递推过程如下 从图中可以看出如果使用普通递归算法想要计算 f(5)f(5)f(5)需要先计算 f(3)f(3)f(3) 和 f(4)f(4)f(4)而在计算 f(4)f(4)f(4) 时还需要计算 f(3)f(3)f(3)。这样 f(3)f(3)f(3) 就进行了多次计算同理 f(0)f(0)f(0)、f(1)f(1)f(1)、f(2)f(2)f(2) 都进行了多次计算从而导致了重复计算问题。 为了避免重复计算在递归的同时我们可以使用一个缓存数组或哈希表来保存已经求解过的 f(k)f(k)f(k) 的结果。如上图所示当递归调用用到 f(k)f(k)f(k) 时先查看一下之前是否已经计算过结果如果已经计算过则直接从缓存中取值返回而不用再递推下去这样就避免了重复计算问题。
我们在使用记忆化搜索解决问题的时候其基本步骤如下
写出问题的动态规划「状态」和「状态转移方程」。定义一个缓存数组或哈希表用于保存子问题的解。定义一个递归函数用于解决问题。在递归函数中首先检查缓存中是否已经存在需要计算的结果如果存在则直接返回结果否则进行计算并将结果存储到缓存中再返回结果。在主函数中调用递归函数并返回结果。
使用「记忆化搜索」方法解决斐波那契数列的代码如下
class Solution:def fib(self, n: int) - int:# 使用数组保存已经求解过的 f(k) 的结果memo [0 for _ in range(n 1)]return self.my_fib(n, memo)def my_fib(self, n: int, memo: List[int]) - int:if n 2:return n# 已经计算过结果if memo[n] ! 0:return memo[n]# 没有计算过结果memo[n] self.my_fib(n - 1, memo) self.my_fib(n - 2, memo)return memo[n]2.2 记忆化搜索与递推的区别
「记忆化搜索」与「递推」都是动态规划的实现方式但是两者之间有一些区别。 记忆化搜索「自顶向下」的解决问题采用自然的递归方式编写过程在过程中会保存每个子问题的解通常保存在一个数组或哈希表中来避免重复计算。 优点代码清晰易懂可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题通过递归调用来解决。缺点可能会因为递归深度过大而导致栈溢出问题。适用场景题的状态转移方程比较复杂递推关系不是很明确问题适合转换为递归形式并且递归深度不会太深。 递推「自底向上」的解决问题采用循环的方式编写过程在过程中通过保存每个子问题的解通常保存在一个数组或哈希表中来避免重复计算。 优点避免了深度过大问题不存在栈溢出问题。计算顺序比较明确易于实现。缺点无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂如果使用递推方法来计算就会导致代码实现变得非常困难。适用场景问题的状态转移方程比较简单递归关系比较明确问题不太适合转换为递归形式或者递归深度过大容易导致栈溢出。
2.3 记忆化搜索的应用
2.3.1 目标和 494. 目标和 - 力扣 给定一个整数数组 numsnumsnums 和一个整数 targettargettarget。数组长度不超过 202020。向数组中每个整数前加 或 -。然后串联起来构造成一个表达式。返回通过上述方法构造的、运算结果等于 targettargettarget 的不同表达式数目。
说明
1≤nums.length≤201 \le nums.length \le 201≤nums.length≤20。0≤nums[i]≤10000 \le nums[i] \le 10000≤nums[i]≤1000。0≤sum(nums[i])≤10000 \le sum(nums[i]) \le 10000≤sum(nums[i])≤1000。−1000≤target≤1000-1000 \le target \le 1000−1000≤target≤1000。
示例
输入nums [1,1,1,1,1], target 3
输出5
解释一共有 5 种方法让最终目标和为 3。
-1 1 1 1 1 3
1 - 1 1 1 1 3
1 1 - 1 1 1 3
1 1 1 - 1 1 3
1 1 1 1 - 1 3思路 1深度优先搜索超时
使用深度优先搜索对每位数字进行 或者 -具体步骤如下
定义从位置 000、和为 000 开始到达数组尾部位置为止和为 targettargettarget 的方案数为 dfs(0, 0)。下面从位置 000、和为 000 开始以深度优先搜索遍历每个位置。如果当前位置 iii 到达最后一个位置 sizesizesize 如果和 cur_sum 等于目标和 targettargettarget则返回方案数 111。如果和 cur_sum 不等于目标和 targettargettarget则返回方案数 000。 递归搜索 i1i 1i1 位置和为 cur_sum - nums[i] 的方案数。递归搜索 i1i 1i1 位置和为 cur_sum nums[i] 的方案数。将 4 ~ 5 两个方案数加起来就是当前位置 iii、和为 cur_sum 的方案数返回该方案数。最终方案数为 dfs(0, 0)将其作为答案返回即可。
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:size len(nums)def dfs(i, cur_sum):if i size:if cur_sum target:return 1else:return 0ans dfs(i 1, cur_sum - nums[i]) dfs(i 1, cur_sum nums[i])return ansreturn dfs(0, 0)时间复杂度O(2n)O(2^n)O(2n)。其中 nnn 为数组 numsnumsnums 的长度。空间复杂度O(n)O(n)O(n)。递归调用的栈空间深度不超过 nnn。
思路 2记忆化搜索 在思路 1 中我们单独使用深度优先搜索对每位数字进行 或者 - 的方法超时了。所以我们考虑使用记忆化搜索的方式避免进行重复搜索。 这里我们使用哈希表 tabletabletable 记录遍历过的位置 iii 及所得到的的当前和cur_sum 下的方案数来避免重复搜索。具体步骤如下
定义从位置 000、和为 000 开始到达数组尾部位置为止和为 targettargettarget 的方案数为 dfs(0, 0)。下面从位置 000、和为 000 开始以深度优先搜索遍历每个位置。如果当前位置 iii 遍历完所有位置 如果和 cur_sum 等于目标和 targettargettarget则返回方案数 111。如果和 cur_sum 不等于目标和 targettargettarget则返回方案数 000。 如果当前位置 iii、和为 cur_sum 之前记录过即使用 tabletabletable 记录过对应方案数则返回该方案数。如果当前位置 iii、和为 cur_sum 之前没有记录过则 递归搜索 i1i 1i1 位置和为 cur_sum - nums[i] 的方案数。递归搜索 i1i 1i1 位置和为 cur_sum nums[i] 的方案数。将上述两个方案数加起来就是当前位置 iii、和为 cur_sum 的方案数将其记录到哈希表 tabletabletable 中并返回该方案数。 最终方案数为 dfs(0, 0)将其作为答案返回
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int:size len(nums)table dict()def dfs(i, cur_sum):if i size:if cur_sum target:return 1else:return 0if (i, cur_sum) in table:return table[(i, cur_sum)]cnt dfs(i 1, cur_sum - nums[i]) dfs(i 1, cur_sum nums[i])table[(i, cur_sum)] cntreturn cntreturn dfs(0, 0)时间复杂度O(2n)O(2^n)O(2n)。其中 nnn 为数组 numsnumsnums 的长度。空间复杂度O(n)O(n)O(n)。递归调用的栈空间深度不超过 nnn。
思路3动态规划
此题也可使用动态规划求解参考《『 一文搞懂 0-1背包问题 』记忆化搜索、动态规划 空间优化》
class Solution:def findTargetSumWays(self, nums: List[int], target: int) - int: pos neg total pos - neg target total sum(nums)if abs(target) total: # target可能为负return 0if (total target) % 2 1: # 不能被2整除【对应于pos不是整数】return 0【0/1背包】从nums中选出数字组成pos或negpos (total target) // 2neg (total - target) // 2capcity min(pos, neg) # 取pos和neg中的较小者以使得dp空间最小n len(nums)# 初始化dp [[0] * (capcity1) for _ in range(n1)]# dp[i][j]: 从前i个元素中选出若干个其和为j的方案数dp[0][0] 1 # 其他 dp[0][j]均为0# 状态更新for i in range(1, n1):for j in range(capcity1):if j nums[i-1]: # 容量有限无法选择第i个数字nums[i-1]dp[i][j] dp[i-1][j]else: # 可选择第i个数字nums[i-1]也可不选【两种方式之和】dp[i][j] dp[i-1][j] dp[i-1][j-nums[i-1]]return dp[n][capcity]2.3.2 第 N 个泰波那契数 1137. 第 N 个泰波那契数 - 力扣 给定一个整数 nnn返回第 nnn 个泰波那契数。
泰波那契数T00,T11,T21T_0 0, T_1 1, T_2 1T00,T11,T21且在 n0n 0n0 的条件下Tn3TnTn1Tn2T_{n 3} T_{n} T_{n1} T_{n2}Tn3TnTn1Tn2。0≤n≤370 \le n \le 370≤n≤37。答案保证是一个 32 位整数即 answer≤231−1answer \le 2^{31} - 1answer≤231−1。
示例
输入n 4
输出4
解释
T_3 0 1 1 2
T_4 1 1 2 4思路 1记忆化搜索
问题的状态定义为第 nnn 个泰波那契数。其状态转移方程为T00,T11,T21T_0 0, T_1 1, T_2 1T00,T11,T21且在 n0n 0n0 的条件下Tn3TnTn1Tn2T_{n 3} T_{n} T_{n1} T_{n2}Tn3TnTn1Tn2。定义一个长度为 n1n 1n1 数组 memomemomemo 用于保存一斤个计算过的泰波那契数。定义递归函数 my_tribonacci(n, memo)。 当 n0n 0n0 或者 n1n 1n1或者 n2n 2n2 时直接返回结果。当 n2n 2n2 时首先检查是否计算过 T(n)T(n)T(n)即判断 memo[n]memo[n]memo[n] 是否等于 000。 如果 memo[n]≠0memo[n] \ne 0memo[n]0说明已经计算过 T(n)T(n)T(n)直接返回 memo[n]memo[n]memo[n]。如果 memo[n]0memo[n] 0memo[n]0说明没有计算过 T(n)T(n)T(n)则递归调用 my_tribonacci(n - 3, memo)、my_tribonacci(n - 2, memo)、my_tribonacci(n - 1, memo)并将计算结果存入 memo[n]memo[n]memo[n] 中并返回 memo[n]memo[n]memo[n]。
class Solution:def tribonacci(self, n: int) - int:# 使用数组保存已经求解过的 T(k) 的结果memo [0 for _ in range(n 1)]return self.my_tribonacci(n, memo)def my_tribonacci(self, n: int, memo: List[int]) - int:if n 0:return 0if n 1 or n 2:return 1if memo[n] ! 0:return memo[n]memo[n] self.my_tribonacci(n - 3, memo) self.my_tribonacci(n - 2, memo) self.my_tribonacci(n - 1, memo)return memo[n]时间复杂度O(n)O(n)O(n)。空间复杂度O(n)O(n)O(n)。
思路二动态规划
class Solution(object):def tribonacci(self, n)::type n: int:rtype: intif n2:return nelif n2:return 1dp[0]*(n1)dp[1]1dp[2]1for i in range(3,n1):dp[i]dp[i-1]dp[i-2]dp[i-3]return dp[n]三、线性动态规划简介 参考动态规划概念和基础线性DP | 潮汐朝夕 线性动态规划具有「线性」阶段划分的动态规划方法统称为线性动态规划简称为「线性 DP」如下图所示。 如果状态包含多个维度但是每个维度上都是线性划分的阶段也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。
线性 DP 问题的划分方法有多种方式。
如果按照「状态的维度数」进行分类我们可以将线性 DP 问题分为一维线性 DP 问题、二维线性 DP 问题以及多维线性 DP 问题。如果按照「问题的输入格式」进行分类我们可以将线性 DP 问题分为单串线性 DP 问题、双串线性 DP 问题、矩阵线性 DP 问题以及无串线性 DP 问题。
本文中我们将按照问题的输入格式进行分类对线性 DP 问题中各种类型问题进行一一讲解。
3.1 单串线性 DP 问题
3.1.1 最长递增子序列 300. 最长递增子序列 - 力扣 单串线性 DP 问题中最经典的问题就是「最长递增子序列Longest Increasing Subsequence简称 LIS」。
给定一个整数数组 numsnumsnums找到其中最长严格递增子序列的长度。
子序列由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7][3,6,2,7][3,6,2,7] 是数组 [0,3,1,6,2,2,7][0,3,1,6,2,2,7][0,3,1,6,2,2,7] 的子序列。1≤nums.length≤25001 \le nums.length \le 25001≤nums.length≤2500。−104≤nums[i]≤104-10^4 \le nums[i] \le 10^4−104≤nums[i]≤104。
示例
输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4。思路 1动态规划 划分阶段 按照子序列的结尾位置进行阶段划分。 定义状态 定义状态 dp[i]dp[i]dp[i] 表示为以 nums[i]nums[i]nums[i] 结尾的最长递增子序列长度。 状态转移方程 一个较小的数后边如果出现一个较大的数则会形成一个更长的递增子序列。对于满足 0≤ji0 \le j i0≤ji 的数组元素 nums[j]nums[j]nums[j] 和 nums[i]nums[i]nums[i] 来说 如果 nums[j]nums[i]nums[j] nums[i]nums[j]nums[i]则 nums[i]nums[i]nums[i] 可以接在 nums[j]nums[j]nums[j] 后面此时以 nums[i]nums[i]nums[i] 结尾的最长递增子序列长度会在「以 nums[j]nums[j]nums[j] 结尾的最长递增子序列长度」的基础上加 111即dp[i]dp[j]1dp[i] dp[j] 1dp[i]dp[j]1。如果 nums[j]≤nums[i]nums[j] \le nums[i]nums[j]≤nums[i]则 nums[i]nums[i]nums[i] 不可以接在 nums[j]nums[j]nums[j] 后面可以直接跳过。
综上我们的状态转移方程为dp[i]max(dp[i],dp[j]1)0≤jinums[j]nums[i]dp[i] max(dp[i], dp[j] 1)0 \le j inums[j] nums[i]dp[i]max(dp[i],dp[j]1)0≤jinums[j]nums[i]。 初始条件 默认状态下把数组中的每个元素都作为长度为 111 的递增子序列。即 dp[i]1dp[i] 1dp[i]1。 最终结果 根据我们之前定义的状态dp[i]dp[i]dp[i] 表示为以 nums[i]nums[i]nums[i] 结尾的最长递增子序列长度。那为了计算出最大的最长递增子序列长度则需要再遍历一遍 dpdpdp 数组求出最大值即为最终结果。
class Solution:def lengthOfLIS(self, nums: List[int]) - int:size len(nums)dp [1 for _ in range(size)]for i in range(size):for j in range(i):if nums[i] nums[j]:dp[i] max(dp[i], dp[j] 1)return max(dp) # 不是dp[n-1]时间复杂度O(n2)O(n^2)O(n2)。两重循环遍历的时间复杂度是 O(n2)O(n^2)O(n2)最后求最大值的时间复杂度是 O(n)O(n)O(n)所以总体时间复杂度为 O(n2)O(n^2)O(n2)。空间复杂度O(n)O(n)O(n)。用到了一维数组保存状态所以总体空间复杂度为 O(n)O(n)O(n)。
3.1.2 最大子数组和 53. 最大子数组和 - 力扣 单串线性 DP 问题中除了子序列相关的线性 DP 问题还有子数组相关的线性 DP 问题。 注意 子序列由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。子数组指的是数组中的一个连续子序列。 「子序列」与「子数组」都可以看做是原数组的一部分而且都不会改变原来数组中元素的相对顺序。其区别在于数组元素是否要求连续。 给定一个整数数组 numsnumsnums,找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组指的是数组中的一个连续部分。1≤nums.length≤1051 \le nums.length \le 10^51≤nums.length≤105。−104≤nums[i]≤104-10^4 \le nums[i] \le 10^4−104≤nums[i]≤104。
示例
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6。3.1.2.1 动态规划 划分阶段 按照连续子数组的结束位置进行阶段划分。 定义状态 定义状态 dp[i]dp[i]dp[i] 为以第 iii 个数结尾的连续子数组的最大和。 状态转移方程 状态 dp[i]dp[i]dp[i] 为以第 iii 个数结尾的连续子数组的最大和。则我们可以从dp[i-1]来讨论 dp[i]。 如果 dp[i - 1] 0则dp[i - 1] nums[i] nums[i]。所以此时 dp[i] 应取第 iii 个数的值即 dp[i] nums[i]。如果 dp[i - 1] ≥0则 dp[i] dp[i - 1] nums[i]。 归纳一下状态转移方程为
dp[i]{nums[i],dp[i−1]0dp[i−1]nums[i]dp[i−1]≥0dp[i] \begin{cases} nums[i], dp[i - 1] 0 \cr dp[i - 1] nums[i] dp[i - 1] \ge 0 \end{cases}dp[i]{nums[i],dp[i−1]nums[i]dp[i−1]0dp[i−1]≥0 初始条件 第 000 个数结尾的连续子数组的最大和为 nums[0]nums[0]nums[0]即 dp[0]nums[0]dp[0] nums[0]dp[0]nums[0]。 最终结果 根据状态定义dp[i]dp[i]dp[i] 为以第 iii 个数结尾的连续子数组的最大和。则最终结果应为所有 dp[i]dp[i]dp[i] 的最大值即 max(dp)max(dp)max(dp)。
class Solution:def maxSubArray(self, nums: List[int]) - int:size len(nums)dp [0 for _ in range(size)]dp[0] nums[0]for i in range(1, size):if dp[i - 1] 0:dp[i] nums[i]else:dp[i] dp[i - 1] nums[i]return max(dp)时间复杂度O(n)O(n)O(n)其中 nnn 为数组 numsnumsnums 的元素个数。空间复杂度O(n)O(n)O(n)。
3.1.2.2 动态规划滚动数组 因为 dp[i]dp[i]dp[i] 只和 dp[i−1]dp[i - 1]dp[i−1] 和当前元素 nums[i]nums[i]nums[i] 相关我们也可以使用一个变量 subMaxsubMaxsubMax 来表示以第 iii 个数结尾的连续子数组的最大和。然后使用 ansMaxansMaxansMax 来保存全局中最大值。
class Solution:def maxSubArray(self, nums: List[int]) - int:size len(nums)subMax nums[0]ansMax nums[0]for i in range(1, size):if subMax 0:subMax nums[i]else:subMax nums[i]ansMax max(ansMax, subMax)return ansMax时间复杂度O(n)O(n)O(n)其中 nnn 为数组 numsnumsnums 的元素个数。空间复杂度O(1)O(1)O(1)。
3.1.3 最长的斐波那契子序列的长度 有一些单串线性 DP 问题在定义状态时需要考虑两个结束位置只考虑一个结束位置的无法清楚描述问题。这时候我们就需要需要增加一个结束位置维度来定义状态。 873. 最长的斐波那契子序列的长度 - 力扣 给定一个严格递增的正整数数组 arrarrarr要求从数组 arrarrarr 中找出最长的斐波那契式的子序列的长度。如果不存斐波那契式的子序列则返回 0。 斐波那契式序列如果序列 X1,X2,...,XnX_1, X_2, ..., X_nX1,X2,...,Xn 满足 n≥3n \ge 3n≥3对于所有 i2≤ni 2 \le ni2≤n都有 XiXi1Xi2X_i X_{i1} X_{i2}XiXi1Xi2则称该序列为斐波那契式序列。 斐波那契式子序列从序列 AAA 中挑选若干元素组成子序列并且子序列满足斐波那契式序列则称该序列为斐波那契式子序列。例如A[3,4,5,6,7,8]A [3, 4, 5, 6, 7, 8]A[3,4,5,6,7,8]。则 [3,5,8][3, 5, 8][3,5,8] 是 AAA 的一个斐波那契式子序列。 3≤arr.length≤10003 \le arr.length \le 10003≤arr.length≤1000。 1≤arr[i]arr[i1]≤1091 \le arr[i] arr[i 1] \le 10^91≤arr[i]arr[i1]≤109。
示例
输入: arr [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18]。3.1.3.1 暴力枚举超时 假设 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]、arr[k]arr[k]arr[k] 是序列 arrarrarr 中的 333 个元素且满足关系arr[i]arr[j]arr[k]arr[i] arr[j] arr[k]arr[i]arr[j]arr[k]则 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]、arr[k]arr[k]arr[k] 就构成了 arrarrarr 的一个斐波那契式子序列。 通过 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]我们可以确定下一个斐波那契式子序列元素的值为 arr[i]arr[j]arr[i] arr[j]arr[i]arr[j]。 因为给定的数组是严格递增的所以对于一个斐波那契式子序列如果确定了 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]则可以顺着 arrarrarr 序列从第 j1j 1j1 的元素开始查找值为 arr[i]arr[j]arr[i] arr[j]arr[i]arr[j] 的元素 。找到 arr[i]arr[j]arr[i] arr[j]arr[i]arr[j] 之后然后再顺着查找子序列的下一个元素。 简单来说就是确定了 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]就能尽可能的得到一个长的斐波那契式子序列此时我们记录下子序列长度。然后对于不同的 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]统计不同的斐波那契式子序列的长度。 最后将这些长度进行比较其中最长的长度就是答案。
class Solution:def lenLongestFibSubseq(self, arr: List[int]) - int:size len(arr)ans 0for i in range(size):for j in range(i 1, size):temp_ans 0temp_i itemp_j jk j 1while k size:if arr[temp_i] arr[temp_j] arr[k]:temp_ans 1temp_i temp_jtemp_j kk 1if temp_ans ans:ans temp_ansif ans 0:return ans 2else:return ans时间复杂度O(n3)O(n^3)O(n3)其中 nnn 为数组 arrarrarr 的元素个数。空间复杂度O(1)O(1)O(1)。
3.1.3.2 哈希表 对于 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j]要查找的元素 arr[i]arr[j]arr[i] arr[j]arr[i]arr[j] 是否在 arrarrarr 中我们可以预先建立一个反向的哈希表。键值对关系为 value:idxvalue : idxvalue:idx这样就能在 O(1)O(1)O(1) 的时间复杂度通过 arr[i]arr[j]arr[i] arr[j]arr[i]arr[j] 的值查找到对应的 arr[k]arr[k]arr[k]而不用像原先一样线性查找 arr[k]arr[k]arr[k] 了。
class Solution:def lenLongestFibSubseq(self, arr: List[int]) - int:size len(arr)ans 0idx_map dict()for idx, value in enumerate(arr):idx_map[value] idxfor i in range(size):for j in range(i 1, size):temp_ans 0temp_i itemp_j jwhile arr[temp_i] arr[temp_j] in idx_map:temp_ans 1k idx_map[arr[temp_i] arr[temp_j]]temp_i temp_jtemp_j kif temp_ans ans:ans temp_ansif ans 0:return ans 2else:return ans时间复杂度O(n2)O(n^2)O(n2)其中 nnn 为数组 arrarrarr 的元素个数。空间复杂度O(n)O(n)O(n)。
3.1.3.3 动态规划 哈希表 划分阶段 按照斐波那契式子序列相邻两项的结尾位置进行阶段划分。 定义状态 定义状态 dp[i][j]dp[i][j]dp[i][j] 表示为以 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j] 为结尾的斐波那契式子序列的最大长度。 状态转移方程 如果arr[i]arr[j]arr[k]arr[i] arr[j] arr[k]arr[i]arr[j]arr[k] 则以 arr[i]arr[i]arr[i]、arr[k]arr[k]arr[k] 结尾的斐波那契式子序列的最大长度等于以 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j] 为结尾的斐波那契式子序列的最大长度加 111。即状态转移方程为dp[j][k]max(A[i]A[j]A[k]ijk)(dp[i][j]1)dp[j][k] max_{(A[i] A[j] A[k]i j k)}(dp[i][j] 1)dp[j][k]max(A[i]A[j]A[k]ijk)(dp[i][j]1)。 初始条件 默认状态下数组中任意相邻两项元素都可以作为长度为 222 的斐波那契式子序列即 dp[i][j]2dp[i][j] 2dp[i][j]2。 最终结果 根据我们之前定义的状态dp[i][j]dp[i][j]dp[i][j] 表示为以 arr[i]arr[i]arr[i]、arr[j]arr[j]arr[j] 为结尾的斐波那契式子序列的最大长度。那为了计算出最大的最长递增子序列长度则需要在进行状态转移时求出最大值 ansansans 即为最终结果。
因为题目定义中斐波那契式中 n≥3n \ge 3n≥3所以只有当 ans≥3ans \ge 3ans≥3 时返回 ansansans。如果 ans3ans 3ans3则返回 000。 注意在进行状态转移的同时我们应和「思路 2哈希表」一样采用哈希表优化的方式来提高效率降低算法的时间复杂度。 class Solution:def lenLongestFibSubseq(self, arr: List[int]) - int:size len(arr)if size3:return 0dp [[0 for _ in range(size)] for _ in range(size)]ans 0# 初始化 dpfor i in range(size):for j in range(i 1, size):dp[i][j] 2d {}# 将 value : idx 映射为哈希表这样可以快速通过 value 获取到 idxfor idx, value in enumerate(arr):d[value] idxfor i in range(size):for j in range(i 1, size):if arr[i] arr[j] in idx_map: # 获取 arr[i] arr[j] 的 idx即斐波那契式子序列下一项元素k d[arr[i] arr[j]]dp[j][k] max(dp[j][k], dp[i][j] 1)ans max(ans, dp[j][k])return ans 时间复杂度O(n2)O(n^2)O(n2)其中 nnn 为数组 arrarrarr 的元素个数。空间复杂度O(n)O(n)O(n)。
3.2 双串线性 DP 问题
双串线性 DP 问题问题的输入为两个数组或两个字符串的线性 DP 问题。状态一般可定义为 dp[i][j]dp[i][j]dp[i][j]表示为
「以第一个数组中第 iii 个位置元素 nums1[i]nums1[i]nums1[i] 为结尾的子数组nums1[0]...nums1[i]nums1[0]...nums1[i]nums1[0]...nums1[i]」与「以第二个数组中第 jjj 个位置元素 nums2[j]nums2[j]nums2[j] 为结尾的子数组nums2[0]...nums2[j]nums2[0]...nums2[j]nums2[0]...nums2[j]」的相关解。「以第一个数组中第 i−1i - 1i−1 个位置元素 nums1[i−1]nums1[i - 1]nums1[i−1] 为结尾的子数组nums1[0]...nums1[i−1]nums1[0]...nums1[i - 1]nums1[0]...nums1[i−1]」与「以第二个数组中第 j−1j - 1j−1 个位置元素 nums2[j−1]nums2[j - 1]nums2[j−1] 为结尾的子数组nums2[0]...nums2[j−1]nums2[0]...nums2[j - 1]nums2[0]...nums2[j−1]」的相关解。「以第一个数组中前 iii 个元素为子数组nums1[0]...nums1[i−1]nums1[0]...nums1[i - 1]nums1[0]...nums1[i−1]」与「以第二个数组中前 jjj 个元素为子数组nums2[0]...nums2[j−1]nums2[0]...nums2[j - 1]nums2[0]...nums2[j−1]」的相关解。
这 333 种状态的定义区别在于相差一个元素 nums1[i]nums1[i]nums1[i] 或 nums2[j]nums2[j]nums2[j]。
第 111 种状态子数组的长度为 i1i 1i1 或 j1j 1j1子数组长度可为空第 222 种状态、第 333 种状态子数组的长度为 iii 或 jjj子数组长度不可为空。
双串线性 DP 问题中最经典的问题就是「最长公共子序列Longest Common Subsequence简称 LCS」。
3.2.1 最长公共子序列 1143. 最长公共子序列 - 力扣 给定两个字符串 text1text1text1 和 text2text2text2要求返回两个字符串的最长公共子序列的长度。如果不存在公共子序列则返回 000。
子序列原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。公共子序列两个字符串所共同拥有的子序列。1≤text1.length,text2.length≤10001 \le text1.length, text2.length \le 10001≤text1.length,text2.length≤1000。text1text1text1 和 text2text2text2 仅由小写英文字符组成。
示例
输入text1 abcde, text2 ace
输出3
解释最长公共子序列是 ace它的长度为 3。思路 1动态规划 划分阶段 按照两个字符串的结尾位置进行阶段划分。 定义状态 定义状态 dp[i][j]dp[i][j]dp[i][j] 表示为「以 text1text1text1 中前 iii 个元素组成的子字符串 str1str1str1 」与「以 text2text2text2 中前 jjj 个元素组成的子字符串 str2str2str2」的最长公共子序列长度为 dp[i][j]dp[i][j]dp[i][j]。 状态转移方程 双重循环遍历字符串 text1text1text1 和 text2text2text2则状态转移方程为 如果 text1[i−1]text2[j−1]text1[i - 1] text2[j - 1]text1[i−1]text2[j−1]说明两个子字符串的最后一位是相同的所以最长公共子序列长度加 111。即dp[i][j]dp[i−1][j−1]1dp[i][j] dp[i - 1][j - 1] 1dp[i][j]dp[i−1][j−1]1。如果 text1[i−1]≠text2[j−1]text1[i - 1] \ne text2[j - 1]text1[i−1]text2[j−1]说明两个子字符串的最后一位是不同的则 dp[i][j]dp[i][j]dp[i][j] 需要考虑以下两种情况取两种情况中最大的那种dp[i][j]max(dp[i−1][j],dp[i][j−1])dp[i][j] max(dp[i - 1][j], dp[i][j - 1])dp[i][j]max(dp[i−1][j],dp[i][j−1])。 str1[0:i−1]str1[0:i-1]str1[0:i−1]与str2[j]str2[j]str2[j]的最长公共子序列长度即 dp[i−1][j]dp[i - 1][j]dp[i−1][j]。str1[0:i]str1[0:i]str1[0:i]与str2[j−1]str2[j-1]str2[j−1]的最长公共子序列长度即 dp[i][j−1]dp[i][j - 1]dp[i][j−1]。 初始条件 当 i0i 0i0 时str1str1str1 表示的是空串空串与 str2str2str2 的最长公共子序列长度为 000即 dp[0][j]0dp[0][j] 0dp[0][j]0。当 j0j 0j0 时str2str2str2 表示的是空串str1str1str1 与 空串的最长公共子序列长度为 000即 dp[i][0]0dp[i][0] 0dp[i][0]0。 最终结果 根据状态定义最后输出 dp[sise1][size2]dp[sise1][size2]dp[sise1][size2]即 text1text1text1 与 text2text2text2 的最长公共子序列长度即可其中 size1size1size1、size2size2size2 分别为 text1text1text1、text2text2text2 的字符串长度。 class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:size1 len(text1)size2 len(text2)dp [[0 for _ in range(size2 1)] for _ in range(size1 1)]for i in range(1, size1 1):for j in range(1, size2 1):if text1[i - 1] text2[j - 1]:dp[i][j] dp[i - 1][j - 1] 1else:dp[i][j] max(dp[i - 1][j], dp[i][j - 1])return dp[size1][size2]时间复杂度O(n×m)O(n \times m)O(n×m)其中 nnn、mmm 分别是字符串 text1text1text1、text2text2text2 的长度。两重循环遍历的时间复杂度是 O(n×m)O(n \times m)O(n×m)所以总的时间复杂度为 O(n×m)O(n \times m)O(n×m)。空间复杂度O(n×m)O(n \times m)O(n×m)。用到了二维数组保存状态所以总体空间复杂度为 O(n×m)O(n \times m)O(n×m)。
3.2.2 最长重复子数组 718. 最长重复子数组 - 力扣 给定两个整数数组 nums1nums1nums1、nums2nums2nums2计算两个数组中公共的、长度最长的子数组长度。
1≤nums1.length,nums2.length≤10001 \le nums1.length, nums2.length \le 10001≤nums1.length,nums2.length≤1000。0≤nums1[i],nums2[i]≤1000 \le nums1[i], nums2[i] \le 1000≤nums1[i],nums2[i]≤100。
示例
输入nums1 [1,2,3,2,1], nums2 [3,2,1,4,7]
输出3
解释长度最长的公共子数组是 [3,2,1] 。思路 1动态规划 划分阶段 按照子数组结尾位置进行阶段划分。 定义状态 定义状态 dp[i][j]dp[i][j]dp[i][j] 为「以 nums1nums1nums1 中前 iii 个元素为子数组nums1[0]...nums2[i−1]nums1[0]...nums2[i - 1]nums1[0]...nums2[i−1]」和「以 nums2nums2nums2 中前 jjj 个元素为子数组nums2[0]...nums2[j−1]nums2[0]...nums2[j - 1]nums2[0]...nums2[j−1]」的最长公共子数组长度。 状态转移方程 如果 nums1[i−1]nums2[j−1]nums1[i - 1] nums2[j - 1]nums1[i−1]nums2[j−1]则当前元素可以构成公共子数组此时 dp[i][j]dp[i−1][j−1]1dp[i][j] dp[i - 1][j - 1] 1dp[i][j]dp[i−1][j−1]1。如果 nums1[i−1]≠nums2[j−1]nums1[i - 1] \ne nums2[j - 1]nums1[i−1]nums2[j−1]则当前元素不能构成公共子数组此时 dp[i][j]0dp[i][j] 0dp[i][j]0。 初始条件 当 i0i 0i0 时nums1[0]...nums1[i−1]nums1[0]...nums1[i - 1]nums1[0]...nums1[i−1] 表示的是空数组空数组与 nums2[0]...nums2[j−1]nums2[0]...nums2[j - 1]nums2[0]...nums2[j−1] 的最长公共子序列长度为 000即 dp[0][j]0dp[0][j] 0dp[0][j]0。当 j0j 0j0 时nums2[0]...nums2[j−1]nums2[0]...nums2[j - 1]nums2[0]...nums2[j−1] 表示的是空数组空数组与 nums1[0]...nums1[i−1]nums1[0]...nums1[i - 1]nums1[0]...nums1[i−1] 的最长公共子序列长度为 000即 dp[i][0]0dp[i][0] 0dp[i][0]0。 最终结果 根据状态定义 dp[i][j]dp[i][j]dp[i][j] 为「以 nums1nums1nums1 中前 iii 个元素为子数组nums1[0]...nums2[i−1]nums1[0]...nums2[i - 1]nums1[0]...nums2[i−1]」和「以 nums2nums2nums2 中前 jjj 个元素为子数组nums2[0]...nums2[j−1]nums2[0]...nums2[j - 1]nums2[0]...nums2[j−1]」的最长公共子数组长度。在遍历过程中我们可以使用 resresres 记录下所有 dp[i][j]dp[i][j]dp[i][j] 中最大值即为答案。
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:size1 len(nums1)size2 len(nums2)dp [[0 for _ in range(size2 1)] for _ in range(size1 1)]res 0for i in range(1, size1 1):for j in range(1, size2 1):if nums1[i - 1] nums2[j - 1]:dp[i][j] dp[i - 1][j - 1] 1if dp[i][j] res:res dp[i][j]return res时间复杂度O(n×m)O(n \times m)O(n×m)。其中 nnn 是数组 nums1nums1nums1 的长度mmm 是数组 nums2nums2nums2 的长度。空间复杂度O(n×m)O(n \times m)O(n×m)。
3.3.3 编辑距离
双串线性 DP 问题中除了经典的最长公共子序列问题之外还包括字符串的模糊匹配问题。 72. 编辑距离 - 力扣 给定两个单词 word1word1word1、word2word2word2。对一个单词可以进行以下三种操作
插入一个字符删除一个字符替换一个字符
请计算出将 word1word1word1 转换为 word2word2word2 所使用的最少操作数。
0≤word1.length,word2.length≤5000 \le word1.length, word2.length \le 5000≤word1.length,word2.length≤500。word1word1word1 和 word2word2word2 由小写英文字母组成。
示例
输入word1 intention, word2 execution
输出5
解释
intention - inention (删除 t)
inention - enention (将 i 替换为 e)
enention - exention (将 n 替换为 x)
exention - exection (将 n 替换为 c)
exection - execution (插入 u)思路 1动态规划 划分阶段 按照两个字符串的结尾位置进行阶段划分。 定义状态 定义状态 dp[i][j]dp[i][j]dp[i][j] 表示为「以 word1word1word1 中前 iii 个字符组成的子字符串 str1str1str1」变为「以 word2word2word2 中前 jjj 个字符组成的子字符串 str2str2str2」所需要的最少操作次数。 状态转移方程 如果当前字符相同word1[i−1]word2[j−1]word1[i - 1] word2[j - 1]word1[i−1]word2[j−1]无需插入、删除、替换。dp[i][j]dp[i−1][j−1]dp[i][j] dp[i - 1][j - 1]dp[i][j]dp[i−1][j−1]。如果当前字符不同word1[i−1]≠word2[j−1]word1[i - 1] \ne word2[j - 1]word1[i−1]word2[j−1]dp[i][j]dp[i][j]dp[i][j] 取源于以下三种情况中的最小情况 替换word1[i−1]word1[i - 1]word1[i−1] 替换为 word2[j−1]word2[j - 1]word2[j−1]最少操作次数依赖于「以 word1word1word1 中前 i−1i - 1i−1 个字符组成的子字符串 str1str1str1」变为「以 word2word2word2 中前 j−1j - 1j−1 个字符组成的子字符串 str2str2str2」再加上替换的操作数 111即dp[i][j]dp[i−1][j−1]1dp[i][j] dp[i - 1][j - 1] 1dp[i][j]dp[i−1][j−1]1。插入word1word1word1 在第 i−1i - 1i−1 位置上插入元素最少操作次数依赖于「以 word1word1word1 中前 i−1i - 1i−1 个字符组成的子字符串 str1str1str1」 变为「以 word2word2word2 中前 jjj 个字符组成的子字符串 str2str2str2」再加上插入需要的操作数 111即dp[i][j]dp[i−1][j]1dp[i][j] dp[i - 1][j] 1dp[i][j]dp[i−1][j]1。删除word1word1word1 删除第 i−1i - 1i−1 位置元素最少操作次数依赖于「以 word1word1word1 中前 iii 个字符组成的子字符串 str1str1str1」变为「以 word2word2word2 中前 j−1j - 1j−1 个字符组成的子字符串 str2str2str2」再加上删除需要的操作数 111即dp[i][j]dp[i][j−1]1dp[i][j] dp[i][j - 1] 1dp[i][j]dp[i][j−1]1。 综合上述情况状态转移方程为
dp[i][j]{dp[i−1][j−1]word1[i−1]word2[j−1]min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])1word1[i−1]≠word2[j−1]dp[i][j] \begin{cases} dp[i - 1][j - 1] word1[i - 1] word2[j - 1] \cr min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1 word1[i - 1] \ne word2[j - 1] \end{cases}dp[i][j]{dp[i−1][j−1]min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])1word1[i−1]word2[j−1]word1[i−1]word2[j−1] 初始条件 当 i0i 0i0 str1str1str1为空字符串str1str1str1变为str2str2str2时至少需要插入 jjj 次即dp[0][j]jdp[0][j] jdp[0][j]j。当 j0j 0j0str2str2str2为空字符串 str1str1str1变为str2str2str2时至少需要删除 iii 次即dp[i][0]idp[i][0] idp[i][0]i。 最终结果 根据状态定义最后输出 dp[sise1][size2]dp[sise1][size2]dp[sise1][size2]即 word1word1word1 变为 word2word2word2 所使用的最少操作数即可。其中 size1size1size1、size2size2size2 分别为 word1word1word1、word2word2word2 的字符串长度。
class Solution:def minDistance(self, word1: str, word2: str) - int:size1 len(word1)size2 len(word2)dp [[0 for _ in range(size2 1)] for _ in range(size1 1)]for i in range(size1 1):dp[i][0] ifor j in range(size2 1):dp[0][j] jfor i in range(1, size1 1):for j in range(1, size2 1):if word1[i - 1] word2[j - 1]:dp[i][j] dp[i - 1][j - 1]else:dp[i][j] min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1return dp[size1][size2]时间复杂度O(n×m)O(n \times m)O(n×m)其中 nnn、mmm 分别是字符串 word1word1word1、word2word2word2 的长度。两重循环遍历的时间复杂度是 O(n×m)O(n \times m)O(n×m)所以总的时间复杂度为 O(n×m)O(n \times m)O(n×m)。空间复杂度O(n×m)O(n \times m)O(n×m)。用到了二维数组保存状态所以总体空间复杂度为 O(n×m)O(n \times m)O(n×m)。
3.3 矩阵线性 DP问题 矩阵线性 DP 问题问题的输入为二维矩阵的线性 DP 问题。状态一般可定义为 dp[i][j]dp[i][j]dp[i][j]表示为从「位置 (0,0)(0, 0)(0,0)」到达「位置 (i,j)(i, j)(i,j)」的相关解。
3.3.1 最小路径和 64. 最小路径和 - 力扣 给定一个包含非负整数的 m×nm \times nm×n 大小的网格 gridgridgrid,找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
每次只能向下或者向右移动一步。mgrid.lengthm grid.lengthmgrid.length。ngrid[i].lengthn grid[i].lengthngrid[i].length。1≤m,n≤2001 \le m, n \le 2001≤m,n≤200。0≤grid[i][j]≤1000 \le grid[i][j] \le 1000≤grid[i][j]≤100。
示例 输入grid [[1,3,1],[1,5,1],[4,2,1]]
输出7
解释因为路径 1→3→1→1→1 的总和最小。思路 1动态规划 划分阶段 按照路径的结尾位置行位置、列位置组成的二维坐标进行阶段划分。 定义状态 定义状态 dp[i][j]dp[i][j]dp[i][j] 为从位置 (0,0)(0, 0)(0,0) 到达位置 (i,j)(i, j)(i,j) 的最小路径和。 状态转移方程 当前位置 (i,j)(i, j)(i,j) 只能从左侧位置 (i,j−1)(i, j - 1)(i,j−1) 或者上方位置 (i−1,j)(i - 1, j)(i−1,j) 到达。为了使得从左上角到达 (i,j)(i, j)(i,j) 位置的最小路径和最小应从 (i,j−1)(i, j - 1)(i,j−1) 位置和 (i−1,j)(i - 1, j)(i−1,j) 位置选择路径和最小的位置达到 (i,j)(i, j)(i,j)。即状态转移方程为dp[i][j]min(dp[i][j−1],dp[i−1][j])grid[i][j]dp[i][j] min(dp[i][j - 1], dp[i - 1][j]) grid[i][j]dp[i][j]min(dp[i][j−1],dp[i−1][j])grid[i][j] 初始条件 当左侧和上方是矩阵边界时即 i0,j0i 0, j 0i0,j0dp[i][j]grid[i][j]dp[i][j] grid[i][j]dp[i][j]grid[i][j]。当只有左侧是矩阵边界时即 i≠0,j0i \ne 0, j 0i0,j0只能从上方到达dp[i][j]dp[i−1][j]grid[i][j]dp[i][j] dp[i - 1][j] grid[i][j]dp[i][j]dp[i−1][j]grid[i][j]。当只有上方是矩阵边界时即 i0,j≠0i 0, j \ne 0i0,j0只能从左侧到达dp[i][j]dp[i][j−1]grid[i][j]dp[i][j] dp[i][j - 1] grid[i][j]dp[i][j]dp[i][j−1]grid[i][j]。 最终结果 根据状态定义最后输出 dp[rows−1][cols−1]dp[rows - 1][cols - 1]dp[rows−1][cols−1]即从左上角到达 (rows−1,cols−1)(rows - 1, cols - 1)(rows−1,cols−1) 位置的最小路径和即可。其中 rowsrowsrows、colscolscols 分别为 gridgridgrid 的行数、列数。
class Solution:def minPathSum(self, grid: List[List[int]]) - int:rows, cols len(grid), len(grid[0])dp [[0 for _ in range(cols)] for _ in range(rows)]dp[0][0] grid[0][0]for i in range(1, rows):dp[i][0] dp[i - 1][0] grid[i][0]for j in range(1, cols):dp[0][j] dp[0][j - 1] grid[0][j]for i in range(1, rows):for j in range(1, cols):dp[i][j] min(dp[i][j - 1], dp[i - 1][j]) grid[i][j]return dp[rows - 1][cols - 1]时间复杂度O(m∗n)O(m * n)O(m∗n)其中 mmm、nnn 分别为 gridgridgrid 的行数和列数。空间复杂度O(m∗n)O(m * n)O(m∗n)。
3.3.2最大正方形 221. 最大正方形 - 力扣 给定一个由 0 和 1 组成的二维矩阵 matrixmatrixmatrix找到只包含 1 的最大正方形并返回其面积。
mmatrix.lengthm matrix.lengthmmatrix.length。nmatrix[i].lengthn matrix[i].lengthnmatrix[i].length。1≤m,n≤3001 \le m, n \le 3001≤m,n≤300。matrix[i][j]matrix[i][j]matrix[i][j] 为 0 或 1。
示例 输入matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
输出4思路 1动态规划 划分阶段 按照正方形的右下角坐标进行阶段划分。 定义状态 定义状态 dp[i][j]dp[i][j]dp[i][j] 表示为以矩阵位置 (i,j)(i, j)(i,j) 为右下角且值包含 111 的正方形的最大边长。 状态转移方程 只有当矩阵位置 (i,j)(i, j)(i,j) 值为 111 时才有可能存在正方形。 如果矩阵位置 (i,j)(i, j)(i,j) 上值为 000则 dp[i][j]0dp[i][j] 0dp[i][j]0。如果矩阵位置 (i,j)(i, j)(i,j) 上值为 111则 dp[i][j]dp[i][j]dp[i][j] 的值由该位置上方、左侧、左上方三者共同约束的为三者中最小值加 111。即dp[i][j]min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])1dp[i][j] min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1dp[i][j]min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])1。 初始条件 默认所有以矩阵位置 (i,j)(i, j)(i,j) 为右下角且值包含 111 的正方形的最大边长都为 000即 dp[i][j]0dp[i][j] 0dp[i][j]0。 最终结果 根据我们之前定义的状态 dp[i][j]dp[i][j]dp[i][j] 表示为以矩阵位置 (i,j)(i, j)(i,j) 为右下角且值包含 111 的正方形的最大边长。则最终结果为所有 dp[i][j]dp[i][j]dp[i][j] 中的最大值。
class Solution:def maximalSquare(self, matrix: List[List[str]]) - int:rows, cols len(matrix), len(matrix[0])max_size 0dp [[0 for _ in range(cols)] for _ in range(rows)]for i in range(rows):for j in range(cols):if matrix[i][j] 1:# 第一行或第一列某个位置为“1”则其dp值为1因为是最小正方形if i 0 or j 0:dp[i][j] 1# 其它位置为“1”时只有左侧、上方和左上方三个位置都是“1”这个位置值才1else:dp[i][j] min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) 1max_size max(max_size, dp[i][j])return max_size * max_size时间复杂度O(m×n)O(m \times n)O(m×n)其中 mmm、nnn 分别为二维矩阵 matrixmatrixmatrix 的行数和列数。空间复杂度O(m×n)O(m \times n)O(m×n)。
3.4无串线性 DP 问题
无串线性 DP 问题问题的输入不是显式的数组或字符串但依然可分解为若干子问题的线性 DP 问题。
3.4.1 整数拆分 343. 整数拆分 - 力扣 给定一个正整数 nnn将其拆分为 k(k≥2)k (k \ge 2)k(k≥2) 个正整数的和并使这些整数的乘积最大化返回可以获得的最大乘积。
2≤n≤582 \le n \le 582≤n≤58。
示例
输入: n 10
输出: 36
解释: 10 3 3 4, 3 × 3 × 4 36。思路 1动态规划 划分阶段 按照正整数进行划分。 定义状态 定义状态 dp[i]dp[i]dp[i] 表示为将正整数 iii 拆分为至少 222 个正整数的和之后这些正整数的最大乘积。 状态转移方程 始终要记得自己定义的dp数组的含义 当 i≥2i \ge 2i≥2 时假设正整数 iii 拆分出的第 111 个正整数是 j(1≤ji)j(1 \le j i)j(1≤ji)则有两种方法 将 iii 拆分为 jjj 和 i−ji - ji−j 的和且 i−ji - ji−j 不再拆分为多个正整数此时乘积为j×(i−j)j \times (i - j)j×(i−j)。将 iii 拆分为 jjj 和 i−ji - ji−j 的和且 i−ji - ji−j 继续拆分为多个正整数此时乘积为j×dp[i−j]j \times dp[i - j]j×dp[i−j]。
则 dp[i]dp[i]dp[i] 取两者中的最大值。即dp[i]max(j×(i−j),j×dp[i−j])dp[i] max(j \times (i - j), j \times dp[i - j])dp[i]max(j×(i−j),j×dp[i−j])。
由于 1≤ji1 \le j i1≤ji需要遍历 jjj 得到 dp[i]dp[i]dp[i] 的最大值则状态转移方程如下
dp[i]max1≤ji{max(j×(i−j),j×dp[i−j])}dp[i] max_{1 \le j i}\lbrace max(j \times (i - j), j \times dp[i - j]) \rbracedp[i]max1≤ji{max(j×(i−j),j×dp[i−j])} 初始条件 000 和 111 都不能被拆分所以 dp[0]0,dp[1]0dp[0] 0, dp[1] 0dp[0]0,dp[1]0。 最终结果 根据我们之前定义的状态dp[i]dp[i]dp[i] 表示为将正整数 iii 拆分为至少 222 个正整数的和之后这些正整数的最大乘积。则最终结果为 dp[n]dp[n]dp[n]。
class Solution:def integerBreak(self, n: int) - int:dp [0 for _ in range(n 1)]for i in range(2, n 1):for j in range(i):dp[i] max(dp[i], (i - j) * j, dp[i - j] * j)return dp[n]时间复杂度O(n2)O(n^2)O(n2)。空间复杂度O(n)O(n)O(n)。
思路 2动态规划优化 思路1中计算dp[i] 时j 的值遍历了从 1 到 i−1 的所有值因此总时间复杂度是O(n2)O(n^2)O(n2)。继续分析可知要想得到最大乘积j只能取2或者3详见《官方题解》则状态转移方程为 dp[i]max(2×(i−2),2×dp[i−2],3×(i−3),3×dp[i−3])dp[i]max(2×(i−2),2×dp[i−2],3×(i−3),3×dp[i−3])dp[i]max(2×(i−2),2×dp[i−2],3×(i−3),3×dp[i−3])
class Solution:def integerBreak(self, n: int) - int:if n 3:return n - 1dp [0] * (n 1)dp[2] 1for i in range(3, n 1):dp[i] max(2 * (i - 2), 2 * dp[i - 2], 3 * (i - 3), 3 * dp[i - 3])return dp[n]3.4.2 只有两个键的键盘
650. 只有两个键的键盘
最初记事本上只有一个字符 A。你每次可以对这个记事本进行两种操作
Copy All复制全部复制这个记事本中的所有字符不允许仅复制部分字符。Paste粘贴粘贴上一次复制的字符。
现在给定一个数字 nnn需要使用最少的操作次数在记事本上输出恰好 nnn 个 A 请返回能够打印出 nnn 个 A 的最少操作次数。 1≤n≤10001 \le n \le 10001≤n≤1000。 示例
输入3
输出3
解释
最初, 只有一个字符 A。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 AA。
第 3 步, 使用 Paste 操作来获得 AAA。思路 1动态规划
class Solution(object):def minSteps(self, n)::type n: int:rtype: intif n1:return 0elif n2:return 2dp[i for i in range(n1)] # 每次复制一个n至多操作n次dp[0]0dp[1]0dp[2]2for i in range(3,n1):for j in range(1,i):if i%j0:dp[i]min(dp[i],dp[j]i//j)return dp[n]其实j是i的因子所以j应该不超过i\sqrt{i}i 。 将其优化
划分阶段
按照字符 A 的个数进行阶段划分。
定义状态
定义状态 dp[i]dp[i]dp[i] 表示为通过「复制」和「粘贴」操作得到 iii 个字符 A最少需要的操作数。 状态转移方程 对于 iii 个字符 A如果 iii 可以被一个小于 iii 的整数 jjj 除尽jjj 是 iii 的因子则说明 jjj 个字符 A 可以通过「复制」「粘贴」总共 ij\frac{i}{j}ji 次得到 iii 个字符 A。而得到 jjj 个字符 A最少需要的操作数可以通过 dp[j]dp[j]dp[j] 获取。
则我们可以枚举 iii 的因子从中找到在满足 jjj 能够整除 iii 的条件下最小的 dp[j]ijdp[j] \frac{i}{j}dp[j]ji即为 dp[i]dp[i]dp[i]即 dp[i]minj∣i(dp[i],dp[j]ij)dp[i] min_{j | i}(dp[i], dp[j] \frac{i}{j})dp[i]minj∣i(dp[i],dp[j]ji)。
由于 jjj 能够整除 iii则 jjj 与 ij\frac{i}{j}ji 都是 iii 的因子两者中必有一个因子是小于等于 i\sqrt{i}i 的所以在枚举 iii 的因子时我们只需要枚举区间 [1,i][1, \sqrt{i}][1,i] 即可。
综上所述状态转移方程为dp[i]minj∣i(dp[i],dp[j]ij,dp[ij]j)dp[i] min_{j | i}(dp[i], dp[j] \frac{i}{j}, dp[\frac{i}{j}] j)dp[i]minj∣i(dp[i],dp[j]ji,dp[ji]j) 初始条件 当 i1i 1i1 时最少需要的操作数为 000。所以 dp[1]0dp[1] 0dp[1]0。 最终结果 根据我们之前定义的状态dp[i]dp[i]dp[i] 表示为通过「复制」和「粘贴」操作得到 iii 个字符 A最少需要的操作数。 所以最终结果为 dp[n]dp[n]dp[n]。
import mathclass Solution:def minSteps(self, n: int) - int:dp [0 for _ in range(n 1)]for i in range(2, n 1):dp[i] float(inf)for j in range(1, int(math.sqrt(n)) 1):if i % j 0:dp[i] min(dp[i], dp[j] i // j, dp[i // j] j)return dp[n]时间复杂度O(nn)O(n \sqrt{n})O(nn)。外层循环遍历的时间复杂度是 O(n)O(n)O(n)内层循环遍历的时间复杂度是 O(n)O(\sqrt{n})O(n)所以总体时间复杂度为 O(nn)O(n \sqrt{n})O(nn)。空间复杂度O(n)O(n)O(n)。用到了一维数组保存状态所以总体空间复杂度为 O(n)O(n)O(n)。
3.5 线性 DP 题目大全
单串线性 DP 问题
题号标题题解标签难度0300最长递增子序列Python二分查找、动态规划中等0673最长递增子序列的个数Python动态规划中等0354俄罗斯套娃信封问题Python动态规划、二分查找困难0053最大子数组和Python数组、分治算法、动态规划简单0152乘积最大子数组Python数组、动态规划中等0918环形子数组的最大和Python数组、动态规划中等0198打家劫舍Python动态规划中等0213打家劫舍 IIPython动态规划中等0740删除并获得点数13883n 块披萨0873最长的斐波那契子序列的长度Python数组、哈希表、动态规划中等1027最长等差数列1055形成字符串的最短路径0368最大整除子集0032最长有效括号Python栈、字符串、动态规划困难0413等差数列划分0091解码方法Python字符串、动态规划中等0639解码方法 IIPython字符串、动态规划困难0132分割回文串 II1220统计元音字母序列的数目Python动态规划困难0338比特位计数Python位运算、动态规划简单0801使序列递增的最小交换次数Python动态规划中等0871最低加油次数0045跳跃游戏 IIPython贪心、数组、动态规划中等0813最大平均值和的分组0887鸡蛋掉落Python数学、二分查找、动态规划困难0256粉刷房子0265粉刷房子 II1473粉刷房子 III0975奇偶跳0403青蛙过河Python数组、动态规划困难1478安排邮筒1230抛掷硬币0410分割数组的最大值Python二分查找、动态规划困难1751最多可以参加的会议数目 II1787使所有区间的异或结果为零0121买卖股票的最佳时机Python数组、动态规划简单0122买卖股票的最佳时机 IIPython数组、贪心算法简单0123买卖股票的最佳时机 IIIPython数组、动态规划困难0188买卖股票的最佳时机 IVPython数组、动态规划困难0309最佳买卖股票时机含冷冻期Python数组、动态规划中等0714买卖股票的最佳时机含手续费Python贪心、数组、动态规划中等
双串线性 DP 问题
题号标题题解标签难度1143最长公共子序列Python字符串、动态规划中等0712两个字符串的最小ASCII删除和0718最长重复子数组Python数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希中等0583两个字符串的删除操作Python字符串、动态规划中等0072编辑距离Python字符串、动态规划困难0044通配符匹配Python贪心、递归、字符串、动态规划困难0010正则表达式匹配Python递归、字符串、动态规划困难0097交错字符串0115不同的子序列Python字符串、动态规划困难0087扰乱字符串
矩阵线性 DP 问题
题号标题题解标签难度0118杨辉三角Python数组简单0119杨辉三角 IIPython数组简单0120三角形最小路径和Python数组、动态规划中等0064最小路径和Python数组、动态规划、矩阵中等0174地下城游戏0221最大正方形Python数组、动态规划、矩阵中等0931下降路径最小和0576出界的路径数Python动态规划中等0085最大矩形0363矩形区域不超过 K 的最大数值和面试题 17.24最大子矩阵1444切披萨的方案数
无串线性 DP 问题
题号标题题解标签难度1137第 N 个泰波那契数Python记忆化搜索、数学、动态规划简单0650只有两个键的键盘Python数学、动态规划中等0264丑数 IIPython哈希表、数学、动态规划、堆优先队列中等0279完全平方数Python广度优先搜索、数学、动态规划中等0343整数拆分Python数学、动态规划中等 文章转载自： http://www.morning.dxsyp.cn.gov.cn.dxsyp.cn http://www.morning.xkjqg.cn.gov.cn.xkjqg.cn http://www.morning.qytyt.cn.gov.cn.qytyt.cn http://www.morning.rtlrz.cn.gov.cn.rtlrz.cn http://www.morning.kzslk.cn.gov.cn.kzslk.cn http://www.morning.xlmpj.cn.gov.cn.xlmpj.cn http://www.morning.sgmis.com.gov.cn.sgmis.com http://www.morning.rldph.cn.gov.cn.rldph.cn http://www.morning.ylpwc.cn.gov.cn.ylpwc.cn http://www.morning.qdrhf.cn.gov.cn.qdrhf.cn http://www.morning.zdkzj.cn.gov.cn.zdkzj.cn http://www.morning.xpqdf.cn.gov.cn.xpqdf.cn http://www.morning.qyqmj.cn.gov.cn.qyqmj.cn http://www.morning.wnjbn.cn.gov.cn.wnjbn.cn http://www.morning.ktblf.cn.gov.cn.ktblf.cn http://www.morning.kpcxj.cn.gov.cn.kpcxj.cn http://www.morning.dgng.cn.gov.cn.dgng.cn http://www.morning.qttft.cn.gov.cn.qttft.cn http://www.morning.sjwqr.cn.gov.cn.sjwqr.cn http://www.morning.rkqzx.cn.gov.cn.rkqzx.cn http://www.morning.gl-group.cn.gov.cn.gl-group.cn http://www.morning.mzpd.cn.gov.cn.mzpd.cn http://www.morning.pxlpt.cn.gov.cn.pxlpt.cn http://www.morning.flxgx.cn.gov.cn.flxgx.cn http://www.morning.slfmp.cn.gov.cn.slfmp.cn http://www.morning.pfmsh.cn.gov.cn.pfmsh.cn http://www.morning.yubkwd.cn.gov.cn.yubkwd.cn http://www.morning.jnptt.cn.gov.cn.jnptt.cn http://www.morning.hqpyt.cn.gov.cn.hqpyt.cn http://www.morning.cknws.cn.gov.cn.cknws.cn http://www.morning.mhmdx.cn.gov.cn.mhmdx.cn http://www.morning.pgcmz.cn.gov.cn.pgcmz.cn http://www.morning.qdxtj.cn.gov.cn.qdxtj.cn http://www.morning.lmfxq.cn.gov.cn.lmfxq.cn http://www.morning.bsrqy.cn.gov.cn.bsrqy.cn http://www.morning.pflry.cn.gov.cn.pflry.cn http://www.morning.frfpx.cn.gov.cn.frfpx.cn http://www.morning.kzhxy.cn.gov.cn.kzhxy.cn http://www.morning.vaqmq.cn.gov.cn.vaqmq.cn http://www.morning.nslwj.cn.gov.cn.nslwj.cn http://www.morning.qyxnf.cn.gov.cn.qyxnf.cn http://www.morning.lrjtx.cn.gov.cn.lrjtx.cn http://www.morning.zrpbf.cn.gov.cn.zrpbf.cn http://www.morning.ylyzk.cn.gov.cn.ylyzk.cn http://www.morning.scjtr.cn.gov.cn.scjtr.cn http://www.morning.trmpj.cn.gov.cn.trmpj.cn http://www.morning.mbmh.cn.gov.cn.mbmh.cn http://www.morning.zlxrg.cn.gov.cn.zlxrg.cn http://www.morning.nxnrt.cn.gov.cn.nxnrt.cn http://www.morning.tlpsd.cn.gov.cn.tlpsd.cn http://www.morning.lwzgn.cn.gov.cn.lwzgn.cn http://www.morning.hbtarq.com.gov.cn.hbtarq.com http://www.morning.qrcxh.cn.gov.cn.qrcxh.cn http://www.morning.gczqt.cn.gov.cn.gczqt.cn http://www.morning.yrmgh.cn.gov.cn.yrmgh.cn http://www.morning.lrmts.cn.gov.cn.lrmts.cn http://www.morning.tdxlj.cn.gov.cn.tdxlj.cn http://www.morning.qkzdc.cn.gov.cn.qkzdc.cn http://www.morning.pkfpl.cn.gov.cn.pkfpl.cn http://www.morning.yxmcx.cn.gov.cn.yxmcx.cn http://www.morning.njddz.cn.gov.cn.njddz.cn http://www.morning.nmyrg.cn.gov.cn.nmyrg.cn http://www.morning.tnjff.cn.gov.cn.tnjff.cn http://www.morning.qkqgj.cn.gov.cn.qkqgj.cn http://www.morning.wyctq.cn.gov.cn.wyctq.cn http://www.morning.drjll.cn.gov.cn.drjll.cn http://www.morning.xqgtd.cn.gov.cn.xqgtd.cn http://www.morning.nfsrs.cn.gov.cn.nfsrs.cn http://www.morning.trqhd.cn.gov.cn.trqhd.cn http://www.morning.fndmk.cn.gov.cn.fndmk.cn http://www.morning.lgtcg.cn.gov.cn.lgtcg.cn http://www.morning.tdwjj.cn.gov.cn.tdwjj.cn http://www.morning.zkgpg.cn.gov.cn.zkgpg.cn http://www.morning.lwmxk.cn.gov.cn.lwmxk.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.mmjqk.cn.gov.cn.mmjqk.cn http://www.morning.mdxwz.cn.gov.cn.mdxwz.cn http://www.morning.lsgsn.cn.gov.cn.lsgsn.cn http://www.morning.dtzxf.cn.gov.cn.dtzxf.cn http://www.morning.bsrcr.cn.gov.cn.bsrcr.cn
