Mid-Autumn festival + National Day to a wave of dynamic planning

preface

Happy Mid-Autumn festival + National Day 🦆

LCP 19. Collection of Autumn Leaves

Xiao Kou went on an autumn trip and collected some red and yellow leaves, which he used to make a preliminary collection of autumn leaves. The string of leaves contains only lowercase characters R and Y, where the character R represents a red leaf and the character Y represents a yellow leaf. For the sake of beauty and tidiness, Xiao Kou wants to adjust the arrangement of leaves in the collection into three parts: “red, yellow and red”. The number of leaves in each part may not be equal, but must be greater than or equal to 1. With each adjustment, Xiaokou can replace a red leaf with a yellow leaf or a yellow leaf with a red leaf. Excuse me, small buckle at least how many times to adjust the operation to collect autumn leaves adjusted.

The sample1: input: leaves ="rrryyyrryyyrr"Output:2Explanation: Adjust twice, replace the two red leaves in the middle with yellow leaves, get"rrryyyyyyyyrr"The sample2: input: leaves ="ryr"Output:0Explanation: Requirements have been met, no additional operations are requiredCopy the code

Tip:

• 3 <= leaves.length <= 10^5
• leavesContains only characters'r'And character'y'

Method 1: Dynamic programming

Algorithm idea:

Since we want to arrange the leaves in the collection into “red, yellow, and red” sections, we can use three states to represent each section separately.

• State 0 State 0 State 0 indicates the red part in front;
• Status 1 Status 1 Indicates the yellow part.
• State 2 State 2 State 2 is the red part behind;

We can try dynamic programming to solve this problem:

1. Define state

The state array f[I][j] represents the minimum number of adjustment operations for the 000th to the 3rd leaf (denoted as leaves[0.. I]) and the 3rd leaf is in state J.

• Iii means terminating subscript (i.e., per leaf)
• JJJ represents: 3 states, 0 for left half (red), 1 for middle half (yellow), 2 for right half (red)

2. DP equation (state transition equation)

We analyze the three states respectively, and the minimum number of substitutions required:

• When j=0j =0j =0, we need to turn the iii leaf red, and the I − 1i-1I −1 leaf can only be in the state j=0j =0j =0, so the state transition equation is:

$f[i][0] = f[i-1][0] + isYellow(i)$

Where isYellow(I)isYellow(I)isYellow(I)is a descriptive function. When leaf I isYellow, it is 1 and when leaf I is red, it is 0.

• When j=1j =1j =1, we need to turn the iii leaf yellow, and the I − 1i-1I −1 leaf can be in the state of j=1j =1j =1 or j=0j =0j =0. We choose the smaller value, so the equation of state is:

$f[i][1] = min\{f[i-1][0], f[i-1][1]\} + isRed(i)$

Where isRed(I) is an indicative function. When leaf I isRed, it is 1 and when leaf I is yellow, it is 0.

• When j=2j =2j =2, we need to turn the iii leaf red, and the I − 1i-1I −1 leaf can be in the state of j=2j =2j =2. It can also be in the state of j=1j =1j =1 (it cannot be in the state of j=0j =0j =0 for cooking fish, because the number of leaves in each state must be at least 1). We choose the smaller value among them, so the state transfer equation is:

$f[i][2] = min\{f[i-1][1], f[i-1][2]\} + isYellow(i)$

Record known state array elements:

1. The first leaf, it has to be the left half, so it just needs to be yellow;
2. The first leaf, must be left half, so f [0] [1] f [0] [1] f [0] [1] and [0] f [2] f [0] [2] f [0] [2] is invalid;
3. The second leaf can be left or middle, but not right (each interval must have leaves), so f[1][2]f[1][2] F [1][2]f[1][2] is invalid.

Reference Code 1:

class Solution {
    public int minimumOperations(String leaves) {
        if (leaves == null || leaves == "") {
            return 0;
        }
        int length = leaves.length();
        char[] chars = leaves.toCharArray();
        [I][j]
        int[][] dp = new int[length][3];

        dp[0] [0] = chars[0] = ='y' ? 1 : 0;
        dp[0] [1] = dp[0] [2] = dp[1] [2] = Integer.MAX_VALUE;

        // Determine whether the current leaf traversed is yellow
        int isYellow = 0;

        // Walk through the collection of leaves
        for (int i = 1; i < length; i++) {
            isYellow = chars[i] == 'y' ? 1 : 0;
            dp[i][0] = dp[i-1] [0] + isYellow;
            dp[i][1] = Math.min(dp[i-1] [0], dp[i-1] [1]) + (1 - isYellow);
            // The right half of the leaf must be the element after the second element
            if (i > 1) {
                dp[i][2] = Math.min(dp[i-1] [1], dp[i-1] [2]) + isYellow; }}// The final result is dp[leng-1][2]
        return dp[length - 1] [2];
    }

Copy the code

Complexity analysis

• Time complexity: O(n)O(n)O(n), where n is the length of the string leaves.
• Space complexity: O(n)O(n)O(n).

Reference Code 2:

By replacing the state array with three variables, the space complexity is reduced to O(1)O(1)O(1).

class Solution {
    public int minimumOperations(String leaves) {
        int n = leaves.length();
        // int[][] f = new int[n][3];
        // f[0][0] = leaves.charAt(0)=='r'? 1-0.
        // f[0][1] = f[0][2] = f[1][2] = 1000000;
        int a = 1000000,b=1000000,c=1000000;
        a = leaves.charAt(0) = ='r'?0:1;
        for(int i=1; i<n; i++){int r = leaves.charAt(i)=='r'?0:1;
            int y = r ^ 1;
            // f[i][0] = f[i-1][0] + r;
            // f[i][1] = Math.min(f[i-1][0],f[i-1][1]) + y;
            // f[i][2] = Math.min(f[i-1][1],f[i-1][2]) + r;
            int aa =a,bb = b,cc = c;
            a += r;
            b = Math.min(aa,bb) + y;
            c = Math.min(bb,cc) + r;
        }
        // return f[n-1][2];
        returnc; }}Copy the code

Some pictures from the network, copyright to the original author, delete.Copy the code