力扣刷题笔记 #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)=\sum_{i=1}^m{a_i}f\left( n-i \right) $，即为齐次线性递推式。本题中的原式可以构造出：

$$\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)$。

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[ 1 \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)$。