[Leetcode][LCP 19][JAVA][秋叶收藏集][动态规划]

太过爱你忘了你带给我的痛 2022-12-12 13:46 64阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

![在这里插入图片描述][20201007111931236.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

###### 1. 动态规划 ######

**时间复杂度：O(N) 空间复杂度：O(N)**

class Solution { 
        public int minimumOperations(String leaves) { 
            if (leaves == null || leaves == "") {    // 排除 不合法参数情况
                return 0;
            }
            int length = leaves.length();
            char[] chars = leaves.toCharArray();
    
            /* 状态数组，state[i][j]中： i表示终止下标 j表示：0为左半边，1为中间部分，2为右半边 state[i][j] 表示 从0到i需要调整的叶子数 */
            int[][] state = new int[length][3];
    
            /* 记录 已知状态数组元素： 1、第一个叶子，必须是左半部分，所以只需判断是不是 黄色叶子 即可 2、第一个叶子，必须是左半部分，所以 state[0][1] 和 state[0][2] 都是无效的 3、第二个叶子，可以是左半部分，也可以是中间部分，但是不能是右半部分(每个区间必须有叶子)， 因此 state[1][2]是无效的 */
            state[0][0] = chars[0] == 'y' ? 1 : 0;
            state[0][1] = state[0][2] = state[1][2] = Integer.MAX_VALUE;
    
            int isYellow = 0;   // 判断 当前遍历的叶子 是不是 黄色
            
            /* 遍历 原叶集，生成状态数组 */
            for (int i = 1; i < length; i++) { 
                isYellow = chars[i] == 'y' ? 1 : 0;
                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 > 1) {     // 右半部分 的叶子 必须是第2个元素之后的元素
                    state[i][2] = Math.min(state[i - 1][1], state[i - 1][2]) + isYellow;
                }
            }
            
            /* 最终结果 为 state[length - 1][2] 因为 state[i][j]最终结果的 i 必须为 length - 1，state[length - 1][j] 中的 j 必须为2 */
            return state[length - 1][2];
        }
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.画图理解 动态规划不可能一步到位的 ######

[【数据结构与算法】【算法思想】动态规划][Link 1]

参考链接：https://leetcode-cn.com/problems/UlBDOe/solution/java-quan-zhu-shi-li-jie-dong-tai-gui-hua-by-leetc/  
参考链接：https://leetcode-cn.com/problems/UlBDOe/solution/dong-tai-gui-hua-java-qiu-xie-shou-cang-ji-by-crus/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/571eb0d5eb7649539128aa988c32ad4b.png
[20201007111931236.png_pic_center]: /images/20221123/6f1e7ed7ed214afd8df2167e7ef4656b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/66e6d7771d324679935cbfa8b21ad58a.png
[Link 1]: https://blog.csdn.net/dadongwudi/article/details/108263805