小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves，
字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，
但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。
请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
示例 1：
输入：leaves = "rrryyyrryyyrr"
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"
示例 2：
输入：leaves = "ryr"
输出：0
解释：已符合要求，不需要额外操作
提示：
3 <= leaves.length <= 10^5
leaves 中只包含字符 'r' 和字符 'y'
自我解答（动态规划）
憋了好久，最后终于做出来了：执行用时：616 ms, 在所有 Python3 提交中击败了84.91%的用户
从最大子序列和中得到启示:
为了简化最优组合问题，转换成以所有元素结尾的最优问题。从中找出原问题最优解
我们知道，要将leaves转换成ryr模式，关键是需要确定两个分界点的最佳位置，以最小代价实现ryr。
显然，与最大子序列和类似，组合的数量太多，不可能都考虑。
转化成另一个最优问题：
fry_(i): 表示以 i 结尾，转化为 ry 模式 的最小变换次数
这么转化的原因在于：
确定了 fry_(i)，就意味着，leaves[i+1:] 需要变换成 r模式, 其变化次数 与 前者相加，
就是一个完整的 ryr 变化次数了，而且，如果从末尾往前遍历，很容易记录下 “变换成 r模式"
的次数，并且遍历过程中，还可以同时考虑 fry_(i)， 一举两得。
如此一来，接下来似乎只需要找出 fry_(i) 和 fry_(i-1) 的 最优子问题结构，这个动态规划
思路就圆满了。的确是的，但也没那么简单，还需要从中再抽象出另一个子问题。
一开始，我思考这两者是否存在简单包含关系：
假设 i 处的叶子是 "r", 这就意味着，需要改成 ”y“，那么这种情况，是否可以直接描述为：
fry_(i) = fry_(i-1) + 1
答案是不行的。
因为 fry_(i-1) 同样是转换成 ry 模式的次数，同样固定住了 leaves[i-1] == "y",
然而，fry_(i)的前一个，可以是 "y", 也可以是 "r", 如：
"rrryyy" 和 "rrrrry"
由此，便可以提炼出一个 ”i 位置前，都是 ‘r’ “ 的子问题，将其描述为 fr_(i-1),
因此，我们就得到了：
当 leaves[i] == "y" 时：
fry_(i) = min(fry_(i-1), fr_(i-1))
当 leaves[i] == "r" 时：
fry_(i) = min(fry_(i-1), fr_(i-1)) + 1
由此，这个动态规划思路便圆满了。
可以设计出自顶向下的递归算法，时间复杂度O(n)
class Solution:
def minimumOperations(self, leaves: str) -> int:
length = len(leaves)
self.leaves = leaves
self.min_num = float("inf")
end_reds = 0
self.r_num = [0] * length
if leaves[0] == "y": self.r_num[0] = 1
if leaves[length - 1] == "y": end_reds += 1
self.get_ry_num(length - 2, end_reds)
return self.min_num
def get_ry_num(self, i, end_reds):
turny, turnr = 0, 0
if self.leaves[i] == "r":
turny = 1
else:
turnr = 1
if i > 1:
ry_num = min(self.get_ry_num(i - 1, end_reds + turnr), self.r_num[i - 1]) + turny
else:
ry_num = self.r_num[i - 1] + turny
self.r_num[i] = self.r_num[i - 1] + 1 if self.leaves[i] == "y" else self.r_num[i - 1]
all_num = ry_num + end_reds
if all_num < self.min_num:
self.min_num = all_num
return ry_num
也可以，自底向上，非递归，省去了递归栈的维护
class Solution2:
def minimumOperations(self, leaves: str) -> int:
length = len(leaves)
min_ryr = float("inf")
_rnums = [0] * (length + 1)
for i in range(length - 1, -1, -1):
plus = 1 if leaves[i] == "y" else 0
_rnums[i] = _rnums[i + 1] + plus
last_rnum = 1 if leaves[0] == "y" else 0
last_min_ry = last_rnum
for i in range(1, length - 1):
turnr = turny = 0
if leaves[i] == "r":
turny = 1
else:
turnr = 1
this_min_ry = min(last_rnum, last_min_ry) + turny
this_min_ryr = this_min_ry + _rnums[i + 1]
if this_min_ryr < min_ryr:
min_ryr = this_min_ryr
last_min_ry = this_min_ry
last_rnum += turnr
return min_ryr