LC 秋叶收藏集

题目链接

想了半天没想出来，看了题解。

两种解法：

1. 三维dp，这个类似套路，寻找状态转移方程，不熟练不容易想出来
2. 推导：这个直观，结合推导，来找效率比较高的算法，是一个通用的思路

定义Y(i)表示以i为结尾的y的个数，R(i)则表示r的个数。

M表示总的y的个数。

那么答案是：

Y(x)+R(y) - R(x) + M - Y(y) = M + [Y(x)-R(x)] - [Y(y)-R(y)] 

那么令g(x)=Y(x)-R(x)，枚举y，然后寻找最小的g(x)，就能得到答案。

计算g(x)，可以维护y和r的计数器，O(1)就得到。 最小的g(x) 满足x<y，只需要维护当前遇到的g(x)的最小值即可，也是O(1)。

所以整体复杂度O(n)，而空间复杂度可以做到O(1)。

class Solution {
    public int minimumOperations(String leaves) {
        int n = leaves.length();
        int mg = 0;
        int cy = 0;
        int cr = 0;
        int ans = n;
        for (int i = 0; i < n; i++) {
            if (leaves.charAt(i) == 'y') {
                cy ++ ;
            } else {
                cr ++;
            }
            int g = cy - cr;

            if (i >= 1 && i < n-1) {
                ans = Math.min(ans, mg - g);
            }

            if (i == 0) {
                mg = g;
            } else {
                mg = Math.min(mg, g);
            }
        }
        return ans + cy;
    }

}

自己想时，其实是按照第二种思路来的，但是没有动笔，也缺乏归纳出g(x)的思路，所以没想出来。 而dp也不太熟练，就没法了。

第三种思路：https://leetcode-cn.com/problems/UlBDOe/comments/588942

同样是推导，不过用枚举区间的长度，和区间内y的个数做参数，转化为最大连续和问题。

最大连续和问题也是dp。