秋叶收藏集

题目描述

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

示例 1：

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

示例 2：

输入： leaves = "ryr" 输出：0

解释：已符合要求，不需要额外操作

解题：动态规划

由于我们想要将收藏集中树叶的排列调整成「红、黄、红」三部分，因此我们可以用 3 个状态分别表示其中的每一部分，即状态 0 和状态 2 分别表示前面和后面的红色部分，状态 1 表示黄色部分。

用 dp[i][j] 表示对于第 0 片到第 i 片叶子进行调整操作的最小次数，并且第 i 片叶子处于状态 j 。

这里面的子问题有 3 个：将 片叶子调整为「红」，「红 - 黄」或「红 - 黄 - 红」的形式。
总问题是：将 n片叶子调整为「红 - 黄 - 红」

那么，状态转移方程可以是：

dp[i][0] = is_yellow(i) + dp[i - 1][0]
dp[i][1] = is_red(i) + min(dp[i - 1][0], dp[i - 1][1])
dp[i][2] = is_yellow(i) + min(dp[i - 1][1], dp[i - 1][2])

启发

动态规划的 dp[i][j] 数组，其下标并不一定是数组的下标，还可以是其他东西，比如这个题里面的状态。