小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r 和 y, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。 出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。 示例 1: 输入:leaves = “rrryyyrryyyrr” 输出:2 解释:调整两次,将中间的两片红叶替换成黄叶,得到 "rrryyyyyyyyrr 示例 2: 输入:leaves = “ryr” 输出:0 解释:已符合要求,不需要额外操作
刚开始是真没想到,没看出来是用动态规划,本来的想法是不断if else,结果还是太年轻了啊,对这种题型也不熟悉的缘故。
经过三次dp遍历。 第一次使得开头至少有一个red。具体做法是每一次发现有yellow就将其转化成red 第二次,在第一次的基础上使得中间,存在yellow。具体做法是index0不变,每一次发现有red就转换成yellow。当然要权衡dp1,和dp2的上一次的次数大小,选择小的做法,每一次转换在自身自增1。 第三次,在第二次的基础上,index0,index1与dp2相同保证开头至少有一个红色,主要防止极端情况下,开头只有一个红,中间只有一个黄色。每一次发现有yellow,转换成red,但是要在dp2的基础上,比较dp3和dp2的次数,选择次数最小的,每一次转换再自增1。 通过三次dp遍历,使得字符串满足要求的情况下,次数还最小。
动态规划还是很难的样子。还是要继续探索写blog。