LeetCode LCP 19 秋葉收藏集 HERODING的LeetCode之路

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

範例 1：

輸入：leaves = "rrryyyrryyyrr"

輸出：2

解釋：調整兩次，將中間的兩片紅葉替換成黃葉，得到 "rrryyyyyyyyrr"

範例 2：

輸入：leaves = "ryr"

輸出：0

解釋：已符合要求，不需要額外操作

提示：

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

解題思路：
這道題目是一個典型的動態規劃題，最複雜的部分當屬dp的構建，dp[i][j]表示在狀態i的情況下，從0到j的順序中
需要調整的最小值，按照這個思路，那麼對於讀入的’r’與’y’就要分開討論，程式碼如下：

class Solution {
public:
    int minimumOperations(string leaves) {
        int INF = 0x3f3f3f3f;
        vector<vector<int>> dp(3, vector<int>(leaves.size(), INF));
        //dp[0]代表第一紅,dp[1]代表第二黃,dp[2]代表第三紅
        if (leaves[0] == 'r') {
            dp[1][0] = 1;
            dp[0][0] = 0;
            //第三個紅色不可能在起始位置，所以必須初始化為無窮
        }
        //同理，第二個黃色不可能在起始位置，初始化INF
        else dp[0][0] = 1;
        for (int i = 1; i < leaves.size(); i++) {
            if (leaves[i] == 'r') {
                dp[0][i] = dp[0][i - 1];
                //dp[1][i] = min(y->y, r->y) + 1 (y變成r次數加1) 前一個是red或者yellow都行
                dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]) + 1;
                //dp[2][i] = min(y->r, r->r) 前一個是yellowyellow或者red都行
                dp[2][i] = min(dp[1][i - 1], dp[2][i - 1]);
            }
            else {
                dp[0][i] = 1 + dp[0][i - 1];
                //dp[1][i] = min(y->y, r->y)
                dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]);
                //dp[2][i] = min(y->r, r->r) + 1 (r變成y次數加1)
                dp[2][i] = min(dp[1][i - 1], dp[2][i - 1]) + 1;
            }
        }
        return dp[2][leaves.size() - 1];
    }
};