秋叶收藏集

动态规划

class Solution {
    public int minimumOperations(String leaves) {
        int n = leaves.length();

        int [][]state = new int[n][3];
        char[] leaveArr = leaves.toCharArray();  
        //状态0：在左边区域需要调整多少次
        //状态1：在中间区域需要调整多少次
        //状态2：在右边区域需要调整多少次
        state[0][0] = leaveArr[0] == 'r'? 0 : 1;
        //必须加否则类似"yry"的样例过不了
        state[0][1] = state[0][2] = state[1][2] = Integer.MAX_VALUE;
        //state[n-1][2] = leaveArr[n-1]
        int isYellow = 0;
        for(int i=1;i<n;i++){
            isYellow = leaveArr[i] == 'r'? 0 : 1;
            state[i][0] = state[i-1][0]+isYellow;
            //左中取最小
            state[i][1] = Math.min(state[i-1][0],state[i-1][1])+1-isYellow;
            //第三片叶子以及之后才可以在右边区域
            //中右取最小
            if(i>=2) state[i][2] = Math.min(state[i-1][2],state[i-1][1])+isYellow;
        }
       return state[n-1][2];
    }
}