Sword finger offer II 092 Flip character / Sword finger offer II 093 Longest Fibonacci sequence

The finger of the sword Offer II 092. Flip the character 【 Medium question 】

Ideas ：【 Dynamic programming 】

Second order dp Array
dp[i][0] It means that the i Bit flip to 0 after , The minimum number of flips the array keeps increasing
dp[i][1] It means that the i Bit flip to 1 after , The minimum number of flips the array keeps increasing

The initial state ：
dp[0][0] = s.charAt(0) == '0' ? 0 : 1
dp[0][1] = s.charAt(0) == '1' ? 0 : 1

Transfer equation ：

dp[i][0] = dp[i-1][0]+s.charAt(i) == '0' ? 0:1
dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1])+s.charAt(i) == '1' ? 0:1

Code ：【dp Array 】

class Solution {
    
    public int minFlipsMonoIncr(String s) {
    
        // Dynamic programming problem solving 
        int n = s.length();
        //dp Two dimensional array 
        // dp[i][0] It means that the i Bit flip to 0 when , Make the string s Monotonically increasing minimum number of flips , here i-1 The character at must be 0
        // dp[i][1] It means that the i Bit flip to 1 when , Make the string s Monotonically increasing minimum number of flips , here i-1 The character at can be 0 It can also be for 1
        int[][] dp = new int[n][2];
        dp[0][0] = s.charAt(0) == '0' ? 0 : 1;// The first 0 The bit character is 0, be dp[0][0]=0, Otherwise 1
        dp[0][1] = s.charAt(0) == '1' ? 0 : 1;// The first 0 The bit character is 1, be dp[0][1]=0, Otherwise 1
        for (int i = 1; i < n; i++) {
    
            int k1 = 0,k2 = 0;
            if (s.charAt(i) == '0'){
    
                k2++;
            }else {
    
                k1++;
            }
            // Will be the first i Bit flip to 0 Minimum number of flips   by  dp[i-1][0] + (s[i] == ‘1’ ？ 1 ： 0)
            dp[i][0] = dp[i-1][0] + k1;
            // Will be the first i Bit flip to 1 Minimum number of flips   by  Math.min(dp[i-1][0],dp[i-1[1]) + (s[i] == '0' ? 1 : 0)
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][1]) + k2;
        }
        // Finally, return to the n-1 Bit flip to 0 Or flip to 1 The lesser of 
        return Math.min(dp[n-1][0],dp[n-1][1]);
    }
}

Code ：【 Scrolling array 】

class Solution {
    
    public int minFlipsMonoIncr(String s) {
    
        // Dynamic programming problem solving 
        int n = s.length();
        // Scrolling array emulation dp Array 
        // dp0 It means that the i Bit flip to 0 when , Make the string s Monotonically increasing minimum number of flips , here i-1 The character at must be 0
        // dp1 It means that the i Bit flip to 1 when , Make the string s Monotonically increasing minimum number of flips , here i-1 The character at can be 0 It can also be for 1
        int dp0 = s.charAt(0) == '0' ? 0 : 1;// The first 0 The bit character is 0, be dp[0][0]=0, Otherwise 1
        int dp1 = s.charAt(0) == '1' ? 0 : 1;// The first 0 The bit character is 1, be dp[0][1]=0, Otherwise 1
        for (int i = 1; i < n; i++) {
    
            int k1 = 0,k2 = 0;
            if (s.charAt(i) == '0'){
    
                k2++;
            }else {
    
                k1++;
            }
            // Will be the first i Bit flip to 0 Minimum number of flips   by  dp[i-1][0] + (s[i] == ‘1’ ？ 1 ： 0)
            k1 += dp0;
            // Will be the first i Bit flip to 1 Minimum number of flips   by  Math.min(dp[i-1][0],dp[i-1[1]) + (s[i] == '0' ? 1 : 0)
            k2 += Math.min(dp0,dp1);
            
            dp0 = k1;
            dp1 = k2;
        }
        // Finally, return to the n-1 Bit flip to 0 Or flip to 1 The lesser of 
        return Math.min(dp0,dp1);
    }
}

---

The finger of the sword Offer II 093. The longest Fibonacci sequence 【 Medium question 】

Ideas ：【 Dynamic programming 】【 Double pointer 】

Refer to the explanation of the question
Dynamic programming + Double pointer , It is fast ！

Code ：

class Solution {
    
    public int lenLongestFibSubseq(int[] arr) {
    
        int n = arr.length,max = 0;
        //dp[i][j] by arr Subscript in array  i j  The position number is the legal Fibonacci sequence at the end ,dp[i][j] The value of represents the length of the Fibonacci sequence 
        int[][] dp = new int[n][n];
        // Traversal array , To traverse the number arr[k] Is the end position of the subsequence of the target legal Fibonacci number sequence 
        for (int k = 2; k < n; k++) {
    
            // Define double pointer  i  and  j  among  i Indicates the starting position of the target legal Fibonacci number sequence subsequence , The initial value is  0,j Represents the first digit of the end position of the target legal Fibonacci number sequence subsequence , The initial value is  k-1
            int i = 0, j = k-1;
            // When  i < j  when , stay [i,j] Whether the in window filter exists   Objective legitimate Fibonacci number sequence subsequence 
            while (i < j){
    
                // When  arr[i] + arr[j] == arr[k] when , It means that we have found a  j k  Legal Fibonacci sequence with position number ending （ Here is abbreviated as jk The goal is ）
                if (arr[i] + arr[j] == arr[k]){
    
                    // If  dp[i][j] == 0  Said to  i j  All subsequences ending with position numbers cannot form a legal Fibonacci sequence , therefore  jk The length of the target can only be  3
                    if (dp[i][j] == 0){
    
                        dp[j][k] = 3;
                    }else {
    
                        // otherwise  jk The length of the target is equal to  ij The length of the target +1  And  jk The length of the target   The maximum between the two 
                        dp[j][k] = Math.max(dp[i][j]+1,dp[j][k]);
                    }
                    // Update at this time max by  max  and  jk Target length   The maximum between the two 
                    max = Math.max(max,dp[j][k]);
                    //i Move the pointer to the right.  j Move the pointer to the left   Continue to search for legal Fibonacci subsequences in the window 
                    i++;
                    j--;
                }else if (arr[i] + arr[j] < arr[k]){
    
                    // When  arr[i] + arr[j] < arr[k] when , according to arr The property of increasing , In order to make  arr[i] + arr[j] ==> arr[k], We should try to shift right i, And then judge again 
                    i++;
                }else {
    
                    // When  arr[i] + arr[j] > arr[k] when , according to arr The property of increasing , In order to make  arr[i] + arr[j] ==> arr[k], We should try to shift left j, And then judge again 
                    j--;
                }
            }
        }
        // Program execution ,max Keep always yes   The maximum length of the legal Fibonacci sequence , Therefore, according to the meaning of the question, the program will return to max that will do 
        return max;
    }
}