2021-04-27：如果一个字符相邻的位置没有相同字符，那么这个位置的字符出现不能被消掉。比如:“ab“

2021-04-27：如果一个字符相邻的位置没有相同字符，那么这个位置的字符出现不能被消掉。比如:"ab"，其中a和b都不能被消掉 。如果一个字符相邻的位置有相同字符，就可以一起消掉。比如:“abbbc”，中间一串的b是可以被消掉的， 消除之后剩下“ac”。某些字符如果消掉了，剩下的字符认为重新靠在一起。给定一个字符串，你可以决定每一步消除的顺序，目标是请尽可能多的消掉字符，返回最少的剩余字符数量。比如："aacca", 如果先消掉最左侧的"aa"，那么将剩下"cca"，然后把"cc"消掉，剩下的"a"将无法再消除，返回1。但是如果先消掉中间的"cc"，那么将剩下"aaa"，最后都消掉就一个字符也不剩了，返回0，这才是最优解。 再比如："baaccabb"，如果先消除最左侧的两个a，剩下"bccabb"，如果再消除最左侧的两个c，剩下"babb"， 最后消除最右侧的两个b，剩下"ba"无法再消除，返回2。而最优策略是：先消除中间的两个c，剩下"baaabb"，再消除中间的三个a，剩下"bbb"，最后消除三个b， 不留下任何字符，返回0，这才是最优解。

福大大 答案2021-04-27：

动态规划。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

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

// 优良尝试的动态规划版本
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
}

执行结果如下：

左神java代码