力扣刷题笔记 #05-1 一维动态规划
本文最后更新于:2023年2月3日 下午
本文包含「动态规划」类型题中的:一维线性 DP、状态机 DP。持续更新中。
题目描述:
方法1:
方法2:
方法3:
坑点:
动态规划(DP)适用于满足重叠子问题 + 最优子结构的问题,常用的解法有自顶向下的「记忆化搜索」、自底向上的「递推」。一旦一个子问题的求解得到结果,以后的计算过程就不会修改它,这样的特点叫做无后效性。DP 的时间复杂度通常是「状态总数 $\times$ 每个状态向其他状态转移的次数」。
动态规划(DP)的一般步骤:
- 列出题目给的整体规模变量,例如 $n,m$
- 用局部变量 $i,j,k$ 描述一般状态,例如 $dp[i][j]$
- 观察上述一般状态的最后一步,例如判断 $s[i]==s[j]$
- 去掉最后一步,问题规模缩小,变成子问题,例如 $dp[i-1][j-1]$
- 得到状态转移方程,例如 $dp[i][j]=dp[i-1][j-1]+1$
- 初始值和最终状态,例如 $dp[i][0]$、$dp[0][j]$ 和 $dp[n][m]$
- 可选的转移优化,例如记忆化、前缀和等
一维线性 DP
简单的一维线性 DP,就是一个递推的序列,当前值由之前的某些值转移而来,如果只由前一个值转移还可以空间优化。
70. 爬楼梯 (E)
题目描述:每次可以爬 1
或 2
个台阶,计算有多少种不同的方法可以爬到第 n
阶。
方法1:DP,$dp[i]$ 表示爬到第 $i$ 阶的方法数,线性递推即可。时空复杂度均为 $O(n)$。
方法2:DP + 空间优化,每个状态只由前两个状态转移,因此可以采用三个变量交替,空间复杂度为 $O(1)$。
方法3:矩阵快速幂,原状态转移方程是齐次线性递推式,因此可以转化为矩阵的递推关系,构造出参数矩阵的 $n$ 次方,使用快速幂加速计算,时间复杂度 $O(\log n)$。
如果一个递归式的形式如 $f(n)=\sum_{i=1}^m{a_i}f\left( n-i \right) $,即为齐次线性递推式。本题中的原式可以构造出:
因此:
方法4:斐波那契通项公式,解出矩阵的两个特征值,代入得通项公式。时间复杂度为幂运算复杂度。
拓展:746. 使用最小花费爬楼梯,题目类似,但是给定一个数组表示从第 i
个台阶向上爬的代价,求爬到楼梯顶的最小代价。此时 $dp[i]$ 就应该表示爬到第 $i$ 阶的最小花费,也是线性递推即可。
121. 买卖股票的最佳时机 (E)
题目描述:给定 prices[]
价格数组,选择某一天购买,并在未来某一天出售,使得利润最大。
方法1:DP,$dp[i]$ 表示前 $i$ 天的最大利润,用一个变量维护此前的最小值,则时空复杂度均为 $O(n)$。
方法2:DP + 空间优化,每个状态只由前一个状态转移过来,因此只需维护一个 $\mathrm{maxProfit}$,空间复杂度 $O(1)$。
96. 不同的二叉搜索树 (M)
题目描述:给定 $n$ 个互不相同的节点值构成二叉搜索树,返回可能的二叉搜索树的种数。
方法1:DP,当数字 $i$ 作为根时,$1$ 到 $i-1$ 的序列作为左子树, $i+1$ 到 $n$ 的序列作为右子树。原问题可以分解成规模较小的两个子问题。初始 $f[0]=f[1]=1$,时间复杂度 $O(n^2)$。
方法2:卡特兰数,$C_0 = 1$,递推式 $C_{n+1}=\frac{2\left( 2n+1 \right)}{n+2}C_n$,时间复杂度 $O(n)$。
264. 丑数 II (M)
题目描述:丑数是只包含质因数 2
、3
和 5
的正整数,返回第 n
个丑数。
方法1:优先队列,维护一个最小堆存储丑数列表,每次弹出堆顶元素后可以生成三个元素(2x
、3x
、5x
)加入最小堆,时间复杂度为 $O(n \log n)$。
方法2:贪心 + DP,每个丑数必然会转移到三个丑数,单看任一种转移方式,小丑数一定先于大丑数转移,因此可以用三个指针来记录三种转移方式当前转移到的丑数。下一个弹出的丑数一定是三者中的最小值。时间复杂度 $O(n)$。
坑点:一个丑数可能会被不同的丑数经过 2x
、3x
、5x
转移到,因此两种方法都会出现重复数字的情况。方法一在入队前要用 unorder_set 来去除重复数字,方法二中的三种转移方式 $dp$ 值可能相等,此时所有相等的指针都要移动。
343. 整数拆分 (M)
题目描述:给定一个正整数 n
,将其拆分为若干个正整数的和,并使这些整数的乘积最大化,返回最大乘积。
方法1:线性 DP,当 $n \geqslant 2$ 时,可以进行拆分,设 $dp[i]$ 表示整数 $i$ 能拆分的最大乘积,则除了 $2$ 和 $3$ 要被初始化为特殊值,其他数都可以由更小的数转移过来。时间复杂度 $O(n^2)$。
方法2:优化 DP,注意到 $i>3$ 时,每个数仅在拆分出 $2$ 或 $3$ 时可能取最优解,因此无需完全遍历,复杂度 $O(n)$。
方法3:数学,通过函数极值证明,当 $n \leqslant 3$ 时,最大乘积只能是 $n-1$;当 $n \geqslant 4$ 时,尽可能将因子三等分时,乘积最大。当被三整除时,直接返回 $3^a$;余数为 $1$ 时,返回 $3^{a-1}\times 4$;余数为 $2$ 时,返回 $3^a \times 2$。时间复杂度 $O(1)$。
139. 单词拆分 (M)
题目描述:给定字符串 s
和单词字典 wordDict
。判断是否可以利用字典中出现的单词拼接出 s
。可重复利用。
方法1:线性 DP + 枚举字典,$dp[i]$ 表示到第 $i$ 个字符位置的子串是否能拼接成功,则初始 $dp[0]=True$,目标是 $dp[n]$。对每个位置都枚举整个字典,直到能使 $dp[i]=True$,时间复杂度 $O(nm)$。
方法2:线性 DP + 枚举子串,$dp[i]$ 同上,但用哈希表存储单词字典,对每个位置都枚举 $0<j<i$,看是否能找到子串 $s[j\cdots i-1]$ 存在于哈希表中,时间复杂度 $O(n^2)$。
940. 不同的子序列 II (H)
题目描述:给定一个字符串 s
,计算 s
的不同非空子序列的个数,子序列不要求连续。
方法1:线性 DP,用一个长度为 26 的数组存放以每个字母结尾的子序列个数,当遇到新字符时更新对应值,时间复杂度为 $O(n\left| \varSigma \right|)$,空间复杂度为 $O(\left| \varSigma \right|)$,$\left| \varSigma \right|$ 为字符集的大小。
观察序列生成,得出以下规律:
- 当遇到一个新字符的时候,将其加到所有已有序列的末尾,即可生成一批完全不重复的序列 Set,Set 内都是以该字符结尾的;
- 如果这个新字符不是第一次出现,那么上次以这个字符为末尾的子序列 oldSet,会被 Set 完全包含,考虑该字符上次出现的位置,也是将其加到所有已有序列的末尾,而这些已有序列会一直存在;
- 但是「这个字符本身」,不会出现在 Set 中,因为 Set 至少长度为 2,因此还要加 1。
方法2:线性 DP + 时间优化,每次更新时都要把 $vec$ 求和,因此用一个变量 $tot$ 维护 $\sum{vec[i]}$,每次将 $vec[c]$ 更新后,再将 $tot$ 的值增加 $vec[c]$ 的变化量即可。时间复杂度优化为 $O(n + \left| \varSigma \right|)$。
1235. 规划兼职工作 (H)
题目描述:有 n
份兼职工作,每份工作预计从 startTime[i]
开始到 endTime[i]
结束,报酬为 profit[i]
。计算可以获得的最大报酬。时间上出现重叠的两份工作不能同时进行。
方法:线性 DP + 二分,这题可以视为活动安排问题的复杂版,多了报酬维度,因此不能贪心,但同样可以按照结束时间排序。设 $dp[i]$ 为第 $i$ 早结束的工作,$dp[0]=0$ 表示一开始没有任何工作可做,时间复杂度 $O(n)$。
本题隐含了离散化的思想,因为时间取值跨度大且不连续,而只有当该时刻有工作结束时才可能更新,其他时刻都会从上一时刻转移。
如果当前时刻 $i$ 有工作结束,要做该工作,则从
startTime[i]
以后就不能再做其他工作,因此要找到比该工作开始时间早结束的工作中最晚的,因此使用upper_bound
。
坑点:分开给的三个数组,如果要合并排序,只需再用一个嵌套数组充当结构体,用下标排序太麻烦了!
状态机 DP
状态机 DP,一维线性 DP 的特例,当前值可能涉及到多个状态序列(持有股票/现金、买卖股票次数、是否交换等),根据当前操作会发生状态序列的切换,如果不操作则保持原序列的上一个状态。由于通常只与前一个值有关,可以进行空间优化。
122. 买卖股票的最佳时机 II (M)
题目描述:给定 prices[]
价格数组,同上,但是可以无限次购买出售,同一时间最多持有一股股票。
方法1:暴力 DFS,每天可以选择是否操作,操作会转变当前状态 cash
或 stock
,时间复杂度 $O(2^n)$,超时。
方法2:状态机 DP,$dp[i][j]$ 表示到下标 $i$ 的这天,持股状态为 $j$ 时,手上拥有的最大现金/盈利数,$j=0$ 表示持有现金,$j=1$ 表示持有股票。显然,最终结果为 $dp[n-1][0]$,初始值为 $dp[0][0]=0$ 和 $dp[0][1]=-\mathrm{prices[0]}$。时空复杂度均为 $O(n)$。
方法3:状态机 DP + 滚动数组,每个状态只由前一维状态转移过来,因此只需维护一个 $\mathrm{preCash}$ 代替 $dp[i-1][0]$,一个 $\mathrm{preStock}$ 替代 $dp[i-1][1]$,最后再同时将二者更新。空间复杂度 $O(1)$。
方法4:贪心,若「day0 买入,day2 卖出」是最优解,拆分成「day0 买入,day1 卖出,day1 买入,day2 卖出」也是最优解。而对于「今天的股价 - 昨天的股价」,贪心选择正数累加即可得到最大值。时间复杂度 $O(n)$,空间复杂度 $O(1)$。
贪心算法是选择那些所有差分(严格)大于 0 的数,把它们相加即可。贪心选择性也很好证明,加上负数的结果一定更小。
坑点:滚动数组中,最好先计算好完整一维再同时更新,除非确保没有依赖,此时二维的滚动数组还能再压缩到一维。
309. 最佳买卖股票时机含冷冻期 (M)
题目描述:给定 prices[]
价格数组,同上,可以无限次购买出售,但每次售出后都会有一天冷冻期,即第二天无法立即买入。同一时间最多持有一股股票。
方法1:状态机 DP,$dp[i][j]$ 表示到下标 $i$ 的这天,持股状态为 $j$ 时,手上拥有的最大现金数,$j=0$ 表示持有现金且非冷冻期,$j=1$ 表示持有股票,$j=2$ 表示持有现金且处于冷冻期。此时,最终结果为 $\max(dp[n][0],dp[n][2])$,初始状态除了 $dp[0][1]=-\mathrm{prices[0]}$ 其他都是零。
方法2:状态机 DP + 滚动数组,每个状态只由前一维状态转移过来,因此只需维护三个变量,最后再同时将三者更新。时间复杂度 $O(n)$,空间复杂度 $O(1)$。
123. 买卖股票的最佳时机 III (M)
题目描述:给定 prices[]
价格数组,同上,但是最多可以完成两笔交易,同一时间最多持有一股股票。
方法1:DP + 贪心,用两个 $dp[i]$ 数组分别计算到下标 $i$ 为止、从下标 $i$ 开始到结束,完成一笔交易的最大利润。将这两个数组相加,得到的 $dp[i]$ 表示以下标 $i$ 天为分界进行两笔交易的最大利润。遗憾的是这种做法仅适用于「两笔交易」。
方法2:状态机 DP + 滚动数组,共有五种状态:未操作、买一次、买卖各一次、买两次卖一次、买卖各两次。第一个状态利润显然为 0,因此可以不用记录。剩下四个状态的最大利润分别记为 $buy1$、$sell1$、$buy2$、$sell2$。复杂度 $O(n)$。
198. 打家劫舍 (M)
题目描述:给定一个非负整数数组 nums
表示每个房子存放的现金,计算小偷在不偷相邻房子的条件下最大偷窃金额。
方法1:状态机 DP,$dp[i][j]$ 表示到下标 $i$ 的房子为止,偷窃状态为 $j$ 时的最大偷窃金额,$j=0$ 表示偷,$j=1$ 表示不偷。时空复杂度均为 $O(n)$。
方法2:状态机 DP + 滚动数组,每个状态只由前一维状态转移过来,因此只需维护两个状态变量,空间复杂度 $O(1)$。
方法3:简化状态方程,利用递归的思想,$dp[i]$ 表示到下标 $i$ 的房子为止的最大偷窃金额,时间复杂度 $O(n)$。
213. 打家劫舍 II (M)
题目描述:同上,但是 N 个房子排成环形。意味着 $nums[0]$ 和 $nums[n-1]$ 是相邻的。
方法1:状态机 DP,由于 $nums[0]$ 和 $nums[n-1]$ 不会同时被偷,本题可以拆成 $[0,n-2]$ 和 $[1, n-1]$ 两个偷窃区间,在两个区间内计算,状态转移方程同上题。时空复杂度均为 $O(n)$。
方法2:状态机 DP + 滚动数组,同上题,空间复杂度 $O(1)$。
152. 乘积最大子数组 (M)
题目描述:给定一个包含正负整数的数组,找出数组中乘积最大的非空连续子数组,返回最大乘积。
方法1:状态机 DP。$f_{\max}$ 和 $f_{\min}$ 表示以第 $i$ 个元素为结尾的最大、最小乘积,均初始化为 $1$,每个元素可以加入前一段或者单独成段,时空复杂度均为 $O(n)$。
考虑只维护一个 $f_{\max}$,如果全为正数,则以第 $i$ 个元素为结尾的状态必然由前一个状态转移(加入或单独成段)。但本题包含正负数,如果当前位置是负数,则当前位置是否单独成段还要考虑接下来还有没有负数。
而从下一个负数的角度出发,我们反而希望维护的前一个状态值也是负数,并且尽可能小,这样负负得正之后 $f_{\max}$ 才能最大。因此必须维护两个状态值,当遇到负数时,两个序列会自动相互转换。
方法2:状态机 DP + 滚动数组,每个状态只由前一维状态转移过来,因此只需维护两个变量,最后再同时将二者更新(用临时变量先存储)。空间复杂度 $O(1)$。
790. 多米诺和托米诺平铺 (M)
题目描述:有两种形状的瓷砖:$2\times 1$ 的长方形,和形如 ∟
的直角型,两种形状都可以旋转。给定整数 $n$,计算用这两种瓷砖铺满 $2\times n$ 的平板的方法数。
方法1:状态机 DP,设 $[1,i-1]$ 列均已全部覆盖,第 $i$ 列状态可能有四种:无覆盖、上方覆盖、下方覆盖、全覆盖。初始时 $dp[0][0]=0,dp[0][1]=0,dp[0][2]=0,dp[0][3]=1$,最后返回 $dp[n][3]$,时间复杂度 $O(n)$。
方法2:构造一维线性 DP,找规律,枚举前几项,从中找规律得到递推式,时间复杂度 $O(n)$。
显然,画出排列方式可知,$f[1]=1,f[2]=2$。而 $f[3]$ 可以转化为 $f[2]+f[1]+2=5$。
同理,$f[4]=f[3]+f[2]+2(f[1]+1)$,这里的 $2$ 作为系数是因为
∟
具有上下对称的特性。$f[5]=f[4]+f[3]+2(f[2]+f[1]+1)=24$,这里发现每次都会加上最近两项,因为有长方形块。
以此类推写出 $f[n-1]$ 和 $f[n]$,两式作差就可以得到递推式。
方法3:滚动数组,空间压缩到 $O(1)$。
TOJ 数数 (M)
题目描述:给定 $n$,求长度为 $n$ 的数字串的个数。要求:每一位为 $1$、$2$ 或 $3$,且不得连续出现三个相同的数字。
方法1:状态机 DP,每一个位置有三种选择,对应以下三种状态,时间复杂度 $O(n)$。
当 $num[i]=1$ 时,$num[i-1]$ 显然可以「取 $2$」、「取 $3$」、「取 $1$ 且 $num[i-2]$ 取 $2$ 或 $3$」。前两者显然就是 $dp\left[ i-1 \right] \left[ 2 \right] +dp\left[ i-1 \right] \left[ 3 \right]$,现在我们想求出第三个项。
注意到当 $num[i-1]=1$ 时,$num[i-2]$ 显然可以「取 $2$」、「取 $3$」、「取 $1$ 且 $num[i-3]$ 取 $2$ 或 $3$」。显然前两者就是我们想要的第三个项,因此用 $dp[i-1][1]$ 扣除 $(dp[i-3][2]+dp[i-3][3])$ 就可以得到目标。
方法2:构造一维线性 DP,将上述状态机 DP 的三个状态相加,得到以下状态转移方程:
方法3:滚动数组,空间压缩到 $O(1)$。
801. 使序列递增的最小交换次数 (H)
题目描述:给定两个长度相等的整数数组,每次操作可以交换两数组相同位置的元素,计算使两个数组均严格递增所需的最小操作次数。(用例保证可以实现严格递增)
方法1:暴力 DFS,有时候必须交换才能满足,有时候可换可不换,此时产生两个分支,时间复杂度 $O(2^n)$,超时。
方法2:状态机 DP,$dp[i][j]$ 表示到下标 $i$ 位置使数组均严格递增的最小操作次数,$j=0$ 表示不换,$j=1$ 表示换。对于每个位置,换和不换两种操作可能都行,取决于相邻两个位置的四个元素以及上一个位置是否发生交换。初始值为 $dp[0][0]=0$ 和 $dp[0][1]=1$,最终返回二者中的较小值。时空复杂度均 $O(n)$。
如果相邻两个位置的四个元素不换还行、换了不行,则位置 $i$ 的交换情况要和位置 $i-1$ 保持一致:
如果必须要换、不换不行,则位置 $i$ 的交换情况要和位置 $i-1$ 相反:
如果换不换都行,则取两种情况中的较小值即可:
方法3:状态机 DP + 滚动数组,每个状态只由前一维状态转移过来,因此只需维护两个变量,最后再同时将二者更新(用临时变量先存储)。空间复杂度 $O(1)$。