LCP19-秋叶收藏集——medium - 《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’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/UlBDOe

思路：
使用动态规划，定义dp[i][j] 保存前0~i个秋叶，将第i个秋叶变为j状态的最小操作数。
dp[i][0]表示将第i个转为红叶,第i-1个叶也必须为红叶。转移方程为：
dp[i][0] = dp[i-1][0] + isRed(i)
dp[i][1]表示将第i个转为黄叶,转移方程为：
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]) + isYellow(i)
dp[i][2]表示将第i个转为红叶，因为题目要求每种颜色每部分树叶数量可以不相等，但均需大于等于 1。所以dp[i][2] 不能由dp[i-1][0]转移得来。转移方程为：
dp[i][1] = Math.min(dp[i-1][1],dp[i-1][2]) +isRed(i)
自然我们最后的答案就是dp[leaves数组长度-1][2]了
再观察可知dp数组可以直接省略数组，由三个变量保存状态，使用数组解构方式完成。

复杂度分析：
时间复杂度O(n)
空间复杂度O(1)

/**
 * @param {string} leaves
 * @return {number}
 */
var minimumOperations = function (leaves) {
    let n = leaves.length;
    let a = Infinity, b = Infinity, c = Infinity;
    a = leaves[0] === "r" ? 0 : 1;
    for (let i = 1; i < n; i++) {
        let isRed = leaves[i] === "r" ? 0 : 1;
        let isYellow = isRed ^ 1;
        [a, b, c] = [
            a + isRed,
            Math.min(a, b) + isYellow,
            Math.min(b, c) + isRed
        ];
    }
    return c;
};