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

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
}