題目來源： Leetcode LCP 19. 秋葉收藏集

一.題目

小扣出去秋游，途中收集了一些紅葉和黃葉，他利用這些葉子初步整理了一份秋葉收藏集 leaves， 字串 leaves 僅包含小寫字符 r 和 y， 其中字符 r 表示一片紅葉，字符 y 表示一片黃葉，
出于美觀整齊的考慮，小扣想要將收藏集中樹葉的排列調整成「紅、黃、紅」三部分，每部分樹葉數量可以不相等，但均需大于等于 1，每次調整操作，小扣可以將一片紅葉替換成黃葉或者將一片黃葉替換成紅葉，請問小扣最少需要多少次調整操作才能將秋葉收藏集調整完畢，

示例 1：
輸入：leaves = "rrryyyrryyyrr"
輸出：2
解釋：調整兩次，將中間的兩片紅葉替換成黃葉，得到 "rrryyyyyyyyrr"

示例 2：
輸入：leaves = "ryr"
輸出：0
解釋：已符合要求，不需要額外操作

提示：

• 3 <= leaves.length <= 10^5
• leaves 中只包含字符 'r' 和字符 'y'

二.解題思路

初看此題可以確定需要將字串分為三段：

• 階段1：r段，此段的黃葉都要替換為紅葉
• 階段2：y段，此段的紅葉都要替換為黃葉
• 階段3：r段，此段的黃葉都要替換為紅葉

而題解即為三段替換次數總和的最小值，那么如何確定這個最小值呢？有分析可知，后一階段的決策要取決于前一階段，因此可以考慮使用動態規劃，具體做法是定義一個 3 × l e n g t h 3\times{length} 3×length的陣列 d p dp dp，其中 l e n g t h length length為字串串長，結構示意圖如下：

其中 d p [ i ] [ 0 ] , d p [ i ] [ 1 ] , d p [ i ] [ 2 ] dp[i][0],dp[i][1],dp[i][2] dp[i][0],dp[i][1],dp[i][2]的含義是第 i i i片葉子處于階段 1 / 2 / 3 1/2/3 1/2/3時處理所需的最小步驟數，由此可知最終結果為 d p [ n ? 1 ] [ 2 ] dp[n-1][2] dp[n?1][2]，因此現在問題就轉變為了確定 d p dp dp表各個階段的值，步驟為：

1. 確定階段1
2. 確定階段2
3. 確定階段3

2.1 階段一

首先，需要確定階段1，對于該階段需要先確認 d p [ 0 ] [ 0 ] dp[0][0] dp[0][0]的值，由題意可得字串leaves的第一個字符必須為'r'，因此可得：
d p [ 0 ] [ 0 ] = { 0 l e a v e s [ 0 ] = = ′ r ′ 1 l e a v e s [ 0 ] = = ′ y ′ dp[0][0]=\begin{cases} 0 & leaves[0] == 'r' \\ 1 & leaves[0]=='y' \\ \end{cases} dp[0][0]={01?leaves[0]==′r′leaves[0]==′y′?
而對于其他處于階段1的元素 d p [ i ] [ 0 ] dp[i][0] dp[i][0]，其遞推計算公式為：
d p [ i ] [ 0 ] = { d p [ i ? 1 ] [ 0 ] l e a v e s [ i ] = = ′ r ′ d p [ i ? 1 ] [ 0 ] + 1 l e a v e s [ i ] = = ′ y ′ dp[i][0]=\begin{cases} dp[i-1][0] & leaves[i] =='r' \\ dp[i-1][0] + 1 & leaves[i]=='y' \\ \end{cases} dp[i][0]={dp[i?1][0]dp[i?1][0]+1?leaves[i]==′r′leaves[i]==′y′?

2.2 階段二

對于階段2，其應從字串leaves的第二個字符開始(前面至少一片紅葉)，其初值 d p [ 1 ] [ 1 ] dp[1][1] dp[1][1]的計算如下：
d p [ 1 ] [ 1 ] = { d p [ 0 ] [ 0 ] + 1 l e a v e s [ 1 ] = = ′ r ′ d p [ 0 ] [ 0 ] l e a v e s [ 1 ] = = ′ y ′ dp[1][1]=\begin{cases} dp[0][0] + 1& leaves[1] == 'r' \\ dp[0][0] & leaves[1]=='y' \\ \end{cases} dp[1][1]={dp[0][0]+1dp[0][0]?leaves[1]==′r′leaves[1]==′y′?
而對于階段2的其他元素 d p [ i ] [ 1 ] dp[i][1] dp[i][1]，由于它的前一個字符可能來自階段2，也可能來自階段1，因此其遞推公式如下：
d p [ i ] [ 1 ] = { m i n ( d p [ i ? 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] ) + 1 l e a v e s [ i ] = = ′ r ′ m i n ( d p [ i ? 1 ] [ 0 ] , d p [ i ? 1 ] [ 1 ] ) l e a v e s [ i ] = = ′ y ′ dp[i][1]=\begin{cases} min(dp[i-1][0], dp[i-1][1]) + 1 & leaves[i] =='r' \\ min(dp[i-1][0], dp[i-1][1]) & leaves[i]=='y' \\ \end{cases} dp[i][1]={min(dp[i?1][0],dp[i?1][1])+1min(dp[i?1][0],dp[i?1][1])?leaves[i]==′r′leaves[i]==′y′?

2.3 階段三

對于階段3，其應從字串leaves的第三個字符開始（前面至少一紅一黃），因此其初值 d p [ 2 ] [ 2 ] dp[2][2] dp[2][2]計算公式如下：
d p [ 2 ] [ 2 ] = { d p [ 1 ] [ 1 ] l e a v e s [ 2 ] = = ′ r ′ d p [ 1 ] [ 1 ] + 1 l e a v e s [ 2 ] = = ′ y ′ dp[2][2]=\begin{cases} dp[1][1] & leaves[2] == 'r' \\ dp[1][1] + 1& leaves[2]=='y' \\ \end{cases} dp[2][2]={dp[1][1]dp[1][1]+1?leaves[2]==′r′leaves[2]==′y′?
而對于階段2的其他元素 d p [ i ] [ 2 ] dp[i][2] dp[i][2]，由于它的前一個字符可能來自階段2，也可能來自階段3，因此其遞推公式如下：
d p [ i ] [ 2 ] = { m i n ( d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 2 ] ) l e a v e s [ i ] = = ′ r ′ m i n ( d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 2 ] ) + 1 l e a v e s [ i ] = = ′ y ′ dp[i][2]=\begin{cases} min(dp[i-1][1], dp[i-1][2]) & leaves[i] =='r' \\ min(dp[i-1][1], dp[i-1][2]) + 1 & leaves[i]=='y' \\ \end{cases} dp[i][2]={min(dp[i?1][1],dp[i?1][2])min(dp[i?1][1],dp[i?1][2])+1?leaves[i]==′r′leaves[i]==′y′?

三.演算法動態運行程序

這里以題目中的示例leaves = "rrryyyrryyyrr"為例進行動態演示，下面是全程序：

階段1初值設定

階段1其他值計算

階段2初值設定

階段2其他值計算

階段3初值設定

階段3其他值計算

四.示例代碼

from typing import List

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n = len(leaves)
        dp = [[0, 0, 0] for _ in range(n)]
        #階段1初值計算
        dp[0][0] = (1 if leaves[0] == 'y' else 0)
        #階段1其他值計算
        for i in range(1, n):
            dp[i][0] = dp[i - 1][0] + (1 if leaves[i] == 'y' else 0)

        #階段2初值計算
        dp[1][1] = dp[0][0] + (1 if leaves[1] == 'r' else 0)
        #階段2其他值計算
        for i in range(2,n):
            dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + (1 if leaves[i] == 'r' else 0)
        
        #階段3初值計算
        dp[2][2] = dp[1][1] + (1 if leaves[2] == 'y' else 0)
        #階段3其他值計算
        for i in range(3,n):
            dp[i][2] = min(dp[i-1][1],dp[i-1][2]) + (1 if leaves[i] == 'y' else 0)
        
        return dp[n - 1][2]

s = Solution()
leaves = "rrryyyrryyyrr"
print(s.minimumOperations(leaves))
"""
2
"""

以上便是本文的全部內容，如果覺得不錯的話，可以點個贊或關注一下博主，后續將會持續更新Leetcode演算法題題解，若是有錯誤的地方，也敬請批評指正!!!