力扣刷题笔记 #05-1 一维动态规划

本文包含「动态规划」类型题中的：一维线性 DP、状态机 DP。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

动态规划（DP）适用于满足重叠子问题 + 最优子结构的问题，常用的解法有自顶向下的「记忆化搜索」、自底向上的「递推」。一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性。DP 的时间复杂度通常是「状态总数 \(\times\) 每个状态向其他状态转移的次数」。

动态规划（DP）的一般步骤：

1. 列出题目给的整体规模变量，例如 \(n,m\)
2. 用局部变量 \(i,j,k\) 描述一般状态，例如 \(dp[i][j]\)
3. 观察上述一般状态的最后一步，例如判断 \(s[i]==s[j]\)
4. 去掉最后一步，问题规模缩小，变成子问题，例如 \(dp[i-1][j-1]\)
5. 得到状态转移方程，例如 \(dp[i][j]=dp[i-1][j-1]+1\)
6. 初始值和最终状态，例如 \(dp[i][0]\)、\(dp[0][j]\) 和 \(dp[n][m]\)
7. 可选的转移优化，例如记忆化、前缀和等

一维线性 DP

简单的一维线性 DP，就是一个递推的序列，当前值由之前的某些值转移而来，如果只由前一个值转移还可以空间优化。

70. 爬楼梯 (E)

题目描述：每次可以爬 1 或 2 个台阶，计算有多少种不同的方法可以爬到第 n 阶。

方法1：DP，\(dp[i]\) 表示爬到第 \(i\) 阶的方法数，线性递推即可。时空复杂度均为 \(O(n)\)。 \[ dp[i]=dp[i-1] + dp[i-2] \] 方法2：DP + 空间优化，每个状态只由前两个状态转移，因此可以采用三个变量交替，空间复杂度为 \(O(1)\)。

方法3：矩阵快速幂，原状态转移方程是齐次线性递推式，因此可以转化为矩阵的递推关系，构造出参数矩阵的 \(n\) 次方，使用快速幂加速计算，时间复杂度 \(O(\log n)\)。

如果一个递归式的形式如 $f(n)=_{i=1}^m{a_i}f( n-i ) $，即为齐次线性递推式。本题中的原式可以构造出： \[ \left[ \begin{array}{c} f(n+1)\\ f(n)\\ \end{array} \right] =\left[ \begin{array}{c} f(n)+f(n-1)\\ f(n)\\ \end{array} \right] =\left[ \begin{matrix} 1& 1\\ 1& 0\\ \end{matrix} \right] \left[ \begin{array}{c} f(n)\\ f(n-1)\\ \end{array} \right] \] 因此： \[ \left[\begin{array}{c} f(n+1) \\ f(n) \end{array}\right]=\left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right]^n\left[\begin{array}{l} f(1) \\ f(0) \end{array}\right] \]

方法4：斐波那契通项公式，解出矩阵的两个特征值，代入得通项公式。时间复杂度为幂运算复杂度。 \[ f(n)=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] \]

拓展：746. 使用最小花费爬楼梯，题目类似，但是给定一个数组表示从第 i 个台阶向上爬的代价，求爬到楼梯顶的最小代价。此时 \(dp[i]\) 就应该表示爬到第 \(i\) 阶的最小花费，也是线性递推即可。 \[ dp[i]=\min(dp[i-1] + cost[i-1],\; dp[i-2] + cost[i-2]) \]

121. 买卖股票的最佳时机 (E)

题目描述：给定 prices[] 价格数组，选择某一天购买，并在未来某一天出售，使得利润最大。

方法1：DP，\(dp[i]\) 表示前 \(i\) 天的最大利润，用一个变量维护此前的最小值，则时空复杂度均为 \(O(n)\)。 \[ dp[i]=\max (dp[i-1],\mathrm{prices}[i]-\mathrm{minPrice}) \] 方法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)\)。 \[ f\left[ n \right] =\sum_{i=1}^n{f\left[ i-1 \right] \times f\left[ n-i \right]} \] 方法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)\)。 \[ dp\left[ i \right] =\min \left\{ dp\left[ p2 \right] \times 2,dp\left[ p3 \right] \times 3,dp\left[ p5 \right] \times 5 \right\} \] 坑点：一个丑数可能会被不同的丑数经过 2x、3x、5x 转移到，因此两种方法都会出现重复数字的情况。方法一在入队前要用 unorder_set 来去除重复数字，方法二中的三种转移方式 \(dp\) 值可能相等，此时所有相等的指针都要移动。

343. 整数拆分 (M)

题目描述：给定一个正整数 n，将其拆分为若干个正整数的和，并使这些整数的乘积最大化，返回最大乘积。

方法1：线性 DP，当 \(n \geqslant 2\) 时，可以进行拆分，设 \(dp[i]\) 表示整数 \(i\) 能拆分的最大乘积，则除了 \(2\) 和 \(3\) 要被初始化为特殊值，其他数都可以由更小的数转移过来。时间复杂度 \(O(n^2)\)。 \[ dp\left[ i \right] =\underset{2\leqslant j<i}{\max}\left( dp\left[ i-j \right] \times j \right) \] 方法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)\)。 \[ dp\left[ i \right] =dp\left[ j \right] \,\,\&\,\, \mathrm{check}\left( s\left[ j\cdots i-1 \right] \right) \] 方法2：线性 DP + 枚举子串，\(dp[i]\) 同上，但用哈希表存储单词字典，对每个位置都枚举 \(0<j<i\)，看是否能找到子串 \(s[j\cdots i-1]\) 存在于哈希表中，时间复杂度 \(O(n^2)\)。

约瑟夫环问题 (M)

题目描述：有 n 个人排成一个环，他们的编号为 0 到 n-1。轮流报数，每次喊到 k 的倍数的人出去，求最后剩下的人。

方法1：模拟，用链表或数组存储编号，用一个计数器表示环，一个计数器数 k。淘汰的时候可以用链表或数组的 erase(nums.begin() + i)。时间复杂度 \(O(nk)\)。

方法2：线性 DP，记 \(dp[i]\) 为 \(i\) 个人的时候最后剩下的人的编号，\(dp[1]=0\) 表示一个人的时候必然是 0 号。如果有 \(i\) 个人，则一个人淘汰后问题规模缩小为 \(i−1\)，且此时会从编号 k%i 开始报数。递推时间复杂度 \(O(n)\)。 \[ dp[i]=(dp[i-1]+k)\;\%\; i \]

940. 不同的子序列 II (H)

题目描述：给定一个字符串 s，计算 s 的不同非空子序列的个数，子序列不要求连续。

方法1：线性 DP，用一个长度为 26 的数组存放以每个字母结尾的子序列个数，当遇到新字符时更新对应值，时间复杂度为 \(O(n\left| \varSigma \right|)\)，空间复杂度为 \(O(\left| \varSigma \right|)\)，\(\left| \varSigma \right|\) 为字符集的大小。 \[ vec[c]=1+\sum{vec[i]} \]

观察序列生成，得出以下规律：

• 当遇到一个新字符的时候，将其加到所有已有序列的末尾，即可生成一批完全不重复的序列 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)\)。 \[ dp[i] = \max \{dp[i-1], dp[k] + profit[i]\} \]

本题隐含了离散化的思想，因为时间取值跨度大且不连续，而只有当该时刻有工作结束时才可能更新，其他时刻都会从上一时刻转移。

如果当前时刻 \(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)\)。 \[ \begin{cases} dp\left[ i \right] \left[ 0 \right] =\max \left( dp\left[ i-1 \right] \left[ 1 \right] +\mathrm{prices}\left[ i \right] , \;\;dp\left[ i-1 \right] \left[ 0 \right] \right)\\ dp\left[ i \right] \left[ 1 \right] =\max \left( dp\left[ i-1 \right] \left[ 0 \right] -\mathrm{prices}\left[ i \right] , \;\;dp\left[ i-1 \right] \left[ 1 \right] \right)\\ \end{cases} \] 方法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]}\) 其他都是零。 \[ \begin{cases} dp\left[ i \right] \left[ 0 \right] =\max \left( dp\left[ i-1 \right] \left[ 0 \right] ,\;\;dp\left[ i-1 \right] \left[ 2 \right] \right)\\ dp\left[ i \right] \left[ 1 \right] =\max \left( dp\left[ i-1 \right] \left[ 0 \right] -\mathrm{prices}\left[ i \right] ,\;\;dp\left[ i-1 \right] \left[ 1 \right] \right)\\ dp\left[ i \right] \left[ 2 \right] =dp\left[ i-1 \right] \left[ 1 \right] +\mathrm{prices}\left[ i \right]\\ \end{cases} \] 方法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)\)。 \[ \left\{ \begin{array}{l} buy_1=\max \left\{ buy_1,\;\;-\mathrm{prices[}i] \right\}\\ sell_1=\max \left\{ sell_1,\;\; buy_1+\mathrm{prices[}i] \right\}\\ buy_2=\max \left\{ buy_2, \;\;sell_1-\mathrm{prices[}i] \right\}\\ sell_2=\max \left\{ sell_2,\;\; buy_2+\mathrm{prices[}i] \right\}\\ \end{array} \right. \]

198. 打家劫舍 (M)

题目描述：给定一个非负整数数组 nums 表示每个房子存放的现金，计算小偷在不偷相邻房子的条件下最大偷窃金额。

方法1：状态机 DP，\(dp[i][j]\) 表示到下标 \(i\) 的房子为止，偷窃状态为 \(j\) 时的最大偷窃金额，\(j=0\) 表示偷，\(j=1\) 表示不偷。时空复杂度均为 \(O(n)\)。 \[ \begin{cases} dp\left[ i \right] \left[ 0 \right] =\max \left( dp\left[ i-1 \right] \left[ 0 \right] ,\;\;dp\left[ i-1 \right] \left[ 1 \right] \right)\\ dp\left[ i \right] \left[ 1 \right] =dp\left[ i-1 \right] \left[ 0 \right] +nums\left[ i \right]\\ \end{cases} \] 方法2：状态机 DP + 滚动数组，每个状态只由前一维状态转移过来，因此只需维护两个状态变量，空间复杂度 \(O(1)\)。

方法3：简化状态方程，利用递归的思想，\(dp[i]\) 表示到下标 \(i\) 的房子为止的最大偷窃金额，时间复杂度 \(O(n)\)。 \[ dp\left[ i \right] =\max \left( dp\left[ i-2 \right]+nums[i] ,\;\;dp\left[ i-1 \right] \right) \]

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)\)。 \[ \begin{aligned} f_{\max }(i) &=\max _{i=1}^n\left\{f_{\max }(i-1) \times a_i, f_{\min }(i-1) \times a_i, a_i\right\} \\ f_{\min }(i) &=\min _{i=1}^n\left\{f_{\max }(i-1) \times a_i, f_{\min }(i-1) \times a_i, a_i\right\} \end{aligned} \]

考虑只维护一个 \(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)\)。 \[ \begin{aligned} dp[i][0]&= dp[i-1][3]\\ dp[i][1]&= dp[i-1][0]+dp[i-1][2]\\ dp[i][2]&= dp[i-1][0]+dp[i-1][1]\\ dp[i][3]&= dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]\\ \end{aligned} \] 方法2：构造一维线性 DP，找规律，枚举前几项，从中找规律得到递推式，时间复杂度 \(O(n)\)。 \[ f[n]=2\times f[n-1]+f[n-3] \]

显然，画出排列方式可知，\(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)\)。 \[ dp\left[ i \right] \left[ 1 \right] =dp\left[ i-1 \right] \left[ 2 \right] +dp\left[ i-1 \right] \left[ 3 \right] +\left( dp\left[ i-1 \right] \left[ 1 \right] -dp\left[ i-3 \right] \left[ 2 \right] -dp\left[ i-3 \right] \left[ 3 \right] \right) \\ dp\left[ i \right] \left[ 2 \right] =dp\left[ i-1 \right] \left[ 1 \right] +dp\left[ i-1 \right] \left[ 3 \right] +\left( dp\left[ i-1 \right] \left[ 2 \right] -dp\left[ i-3 \right] \left[ 1 \right] -dp\left[ i-3 \right] \left[ 3 \right] \right) \\ dp\left[ i \right] \left[ 3 \right] =dp\left[ i-1 \right] \left[ 1 \right] +dp\left[ i-1 \right] \left[ 2 \right] +\left( dp\left[ i-1 \right] \left[ 3 \right] -dp\left[ i-3 \right] \left[ 1 \right] -dp\left[ i-3 \right] \left[ 2 \right] \right) \]

当 \(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 的三个状态相加，得到以下状态转移方程： \[ dp[i] = 3 \times dp[i - 1] - 2 \times dp[i - 3] \] 方法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\) 保持一致： \[ \left\{\begin{array}{l} d p[i][0]=d p[i-1][0] \\ d p[i][1]=d p[i-1][1]+1 \end{array}\right. \] 如果必须要换、不换不行，则位置 \(i\) 的交换情况要和位置 \(i-1\) 相反： \[ \left\{\begin{array}{l} d p[i][0]=d p[i-1][1] \\ d p[i][1]=d p[i-1][0]+1 \end{array}\right. \] 如果换不换都行，则取两种情况中的较小值即可： \[ \left\{\begin{array}{l} d p[i][0]=\min \{d p[i-1][0], d p[i-1][1]\} \\ d p[i][1]=\min \{d p[i-1][1], d p[i-1][0]\}+1 \end{array}\right. \]

方法3：状态机 DP + 滚动数组，每个状态只由前一维状态转移过来，因此只需维护两个变量，最后再同时将二者更新（用临时变量先存储）。空间复杂度 \(O(1)\)。