一个子序列的消除规则如下:
1、在某一个子序列中，如果’1’的左边有’0’，那么这两个字符->“01"可以消除；
2、 在某一个子序列中，如果’3’的左边有’2’，那么这两个字符->“23"可以消除；
3、当这个子序列的某个部分消除之后，认为其他字符会自动贴在一起，可以继续寻找消除的机会。
比如，某个子序列"0231”，先消除掉"23”，那么剩下的字符贴在一起变成"01"，继续消除就没有字符了，
如果某个子序列通过最优良的方式，可以都消掉，那么这样的子序列叫做“全消子序列”，
一个只由’0’、‘1’、‘2’、'3’四种字符组成的字符串str，可以生成很多子序列，返回“全消子序列”的最大长度，
字符串str长度 <= 200。
递归。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
str1 := "010101"
fmt.Println(maxDisappear(str1))
str2 := "021331"
fmt.Println(maxDisappear(str2))
}
// str[L...R]上，都能消掉的子序列，最长是多少？
func f(str string, L, R int) int {
if L >= R {
return 0
}
if L == R-1 {
if (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') {
return 2
} else {
return 0
}
//return (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') ? 2 : 0;
}
// L...R 有若干个字符 > 2
// str[L...R]上，都能消掉的子序列，最长是多少？
// 可能性1，能消掉的子序列完全不考虑str[L]，最长是多少？
p1 := f(str, L+1, R)
if str[L] == '1' || str[L] == '3' {
return p1
}
// str[L] =='0' 或者 '2'
// '0' 去找 '1'
// '2' 去找 '3'
find := byte('1')
if str[L] != '0' {
find = '3'
}
//find := str[L] == '0' ? '1' : '3';
p2 := 0
// L() ......
for i := L + 1; i <= R; i++ {
// L(0) ..... i(1) i+1....R
if str[i] == find {
p2 = getMax(p2, f(str, L+1, i-1)+2+f(str, i+1, R))
}
}
return getMax(p1, p2)
}
func maxDisappear(str string) int {
if len(str) == 0 {
return 0
}
return disappear(str, 0, len(str)-1)
}
// s[l..r]范围上，如题目所说的方式，最长的都能消掉的子序列长度
func disappear(s string, l, r int) int {
if l >= r {
return 0
}
if l == r-1 {
if (s[l] == '0' && s[r] == '1') || (s[l] == '2' && s[r] == '3') {
return 2
} else {
return 0
}
//return (s[l] == '0' && s[r] == '1') || (s[l] == '2' && s[r] == '3') ? 2 : 0;
}
p1 := disappear(s, l+1, r)
if s[l] == '1' || s[l] == '3' {
return p1
}
p2 := 0
find := byte('1')
if s[l] != '0' {
find = '3'
}
//find := s[l] == '0' ? '1' : '3';
for i := l + 1; i <= r; i++ {
if s[i] == find {
p2 = getMax(p2, disappear(s, l+1, i-1)+2+disappear(s, i+1, r))
}
}
return getMax(p1, p2)
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
