题解 | #[CQOI2007]涂色PAINT#

package main

import (
	"fmt"
)

const INF = 100

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var str string
	var dp [55][55]int
	fmt.Scan(&str)
	lens := len(str)
	str = " " + str
	for i := 0; i <= lens+2; i++ {
		for j := 0; j <= lens+2; j++ {
			dp[i][j] = INF
			dp[i][j] = INF
		}
	}
	for i := lens; i > 0; i-- {
		dp[i][i] = 1
		for j := i + 1; j <= lens; j++ {
			if str[i] == str[i+1] {
				dp[i][j] = min(dp[i][j], dp[i+1][j])
			}
			if str[i] == str[j] {
				dp[i][j] = min(dp[i][j], dp[i+1][j])
			}
			if str[j] == str[i] {
				dp[i][j] = min(dp[i][j], dp[i][j-1])
			}
			if str[j] == str[j-1] {
				dp[i][j] = min(dp[i][j], dp[i][j-1])
			}
            for k := i;  k < j; k++{
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
            }
		}
	}
    fmt.Println(dp[1][lens])
}