秋叶收藏集

难度中等

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

示例 1：
输入：leaves = “rrryyyrryyyrr”
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 “rrryyyyyyyyrr”

示例 2：
输入：leaves = “ryr”
输出：0
解释：已符合要求，不需要额外操作

提示：
3 <= leaves.length <= 10^5
leaves 中只包含字符 ‘r’ 和字符 ‘y’

思路

一开始的思路就是单纯的通过几次迭代找出左边出现 r 和 y 的相关信息和右边出现 r 和 y 的相关信息，然后对所有情况进行讨论，结果发现，情况好多，需要判断的很多

经过一番斗争，，，，，发现最合适的还是用动态规划，感觉只要题中出现求最少或者最多的都可以用DP，因为动态规划的初衷就是通过一些已经计算好的信息去寻找一个最优解。
既然想着可以用DP，那么就需要寻找状态，因为我们需要将字符串整成【红，黄，红】的排列，所以可以定义三个状态：用０和２表示前面的红色和后面的红色，用１表示中间的黄色

• 之后我们可以定义一个二维数组 int[leaves.length()][3]，dp[i][j]表示 leaves[0…..i] 的字符串状态为 j 的最小操作次数
• 首先是状态 0 ，即前面的部分是[红]，那当前 dp[i][0] 就取决于前面一个字符在状态0时的最小操作次数加上本位上是否是红色！
• 然后是状态 1 ，即前面的部分是[红,黄]， 那当前 dp[i][1] 就是要取前面一个字符处于状态 0 和状态 1 的最小值 ( 因为前面是【红】还是 【红，黄】都可以，毕竟本位上一定会调整为黄，而使0….i一定为状态 1 ！)加上本位是否是黄色！
• 最终是状态 2，即前面的部分是[红，黄，红]!， 那当前 dp[i][2] 就是取前面一个字符处于状态 1 和状态 2 的最小值（*因为状态 1 是【红，黄】，状态 2 是 【红，黄，红】都满足条件的，毕竟本位最终会调整为 红色，使 0…i 一定满足【红，黄，红】，而状态 0 是不行的，因为 【红】的情况再怎么调整也无法调整为 【红，黄，红】！ *） 加上本位是否是红色！

注意

由于 因为每一种状态包含的叶子数量必须至少为 1，因此不仅需要特别注意 j=2 时的状态转移方程，还需要考虑每个状态本身是否是符合要求的。对于状态 dp[i][j]而言，它包含了leaves[ 0..i ] 共 i+1 片叶子以及 j+1 个状态，因此 叶子的数量必须大于等于状态的数量，即满足 i≥j。 这样一来，所有 i < j 的状态 dp[i][j] 都是不符合要求的。 观察上面的状态转移方程，我们在每一步转移时都是取最小值，因此我们可以将所有不符合要求的状态置为一个极大值（例如 n+1 或整数类型的上限等）。

这种利用以前的状态信息来加速本位上的状态收集，并最终求出最优解的方法就是dp，所以至关重要的是如何找出正确的状态，以及状态方程！

下面展示一下代码：

class Solution {
    public int minimumOperations(String leaves) {
        int len = leaves.length();
        int[][] dp = new int[len][3];
        dp[0][0] = leaves.charAt(0) == 'y' ? 1 : 0;
        dp[0][1] = dp[0][2] = dp[1][2] = Integer.MAX_VALUE;//需要注意这点，即叶子的数量一定是大于等于状态的总数的！
        for (int i = 1; i < n; ++i) {
            int isRed = leaves.charAt(i) == 'r' ? 1 : 0;
            int isYellow = leaves.charAt(i) == 'y' ? 1 : 0;
            //以下这三步需要好好体会！
            dp[i][0] = dp[i - 1][0] + isYellow;
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + isRed;
            if (i >= 2) {
               dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][2]) + isYellow;
            }
        }
        return dp[len - 1][2];
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接