2021-04-27: if the adjacent position of a character does not have the same character

2021-04-27： If there is no same character in the adjacent position of a character , Then the character in this position cannot be eliminated . such as :"ab", among a and b Can not be eliminated . If a character has the same character adjacent to it , Can be eliminated together . such as :“abbbc”, The middle string b Can be eliminated , After elimination, there are still “ac”. If some characters are eliminated , The rest of the characters are thought to lean back together . Given a string , You can decide the order of elimination of each step , The goal is to eliminate as many characters as possible , Returns the minimum number of remaining characters . such as ："aacca", If you eliminate the leftmost first "aa", Then there will be "cca", And then put "cc" Eliminate , The rest "a" Will no longer be able to eliminate , return 1. But if you eliminate the middle first "cc", Then there will be "aaa", Finally, all of them are eliminated, and there is no character left , return 0, This is the best solution . Another example ："baaccabb", If you eliminate the leftmost two first a, be left over "bccabb", If you eliminate the two leftmost c, be left over "babb", Finally, eliminate the two on the far right b, be left over "ba" Can no longer eliminate , return 2. And the best strategy is ： First eliminate the two in the middle c, be left over "baaabb", Eliminate the middle three a, be left over "bbb", Finally, eliminate three b, Leave no characters , return 0, This is the best solution .

Fuda answer 2021-04-27：

Dynamic programming .

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "math"
)

func main() {
    s := "aabbac"
    ret := restMin(s)
    fmt.Println(ret)
}

//  A dynamic programming version of a good attempt 
func restMin(s string) int {

    if len(s) < 2 {
        return len(s)
    }

    N := len(s)
    dp := make([][][]int, N)
    for i := 0; i < N; i++ {
        dp[i] = make([][]int, N)
        for j := 0; j < N; j++ {
            dp[i][j] = make([]int, 2)
        }
    }
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            for k := 0; k < 2; k++ {
                dp[i][j][k] = -1
            }
        }
    }
    return dpProcess(s, 0, N-1, false, dp)
}
func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}
func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}
func dpProcess(str string, L int, R int, has bool, dp [][][]int) int {
    if L > R {
        return 0
    }

    K := twoSelectOne(has, 1, 0)

    if dp[L][R][K] != -1 {
        return dp[L][R][K]
    }
    ans := 0
    if L == R {

        ans = twoSelectOne(K == 0, 1, 0)
    } else {
        index := L
        all := K
        for index <= R && str[index] == str[L] {
            all++
            index++
        }
        way1 := twoSelectOne(all > 1, 0, 1) + dpProcess(str, index, R, false, dp)
        way2 := math.MaxInt64
        for split := index; split <= R; split++ {
            if str[split] == str[L] && str[split] != str[split-1] {
                if dpProcess(str, index, split-1, false, dp) == 0 {
                    way2 = getMin(way2, dpProcess(str, split, R, all > 0, dp))
                }
            }
        }
        ans = getMin(way1, way2)
    }
    dp[L][R][K] = ans
    return ans
}

The results are as follows ：

Insert picture description here

---

Zuo Shen java Code