题解 | #[CQOI2007]涂色PAINT#

思路，本题用动态规划来做，dp[l][r]就是以s[l]和s[r]为结尾的字符串最少的颜色涂法。我们要求的字符串厂度为n,所以s[l]和s[r]之间的距离就为n，问题很复杂。

• 我们现在来减小问题规模，如果s[l]等于s[r]也就是说字符串两端的的字符相同，这两端的两个字符记录一次涂改。
• 若不同则在l和r之间我们选取一点K，s[l]和s[r]为结尾的字符串最少的颜色涂法就成了s[l]和s[k], s[k + 1]和s[r] 之间的最少涂法。
• 在不断切分下，问题最终会变成s[l]等于s[k]等于s[r]，即只剩一个字符的情况。此时涂法只有一种。这种情况就是dp需要的初始化。 动态转移方程则可分为两部分，当子字符串s[l:r]的左边s[l]和右边s[r]相等时dp[l][r] = min(dp[l][r - 1], dp[l + 1][r])。就是s[l:r]的最小涂色方案是其子字符串s[l:r - 1]和s[l + 1:r]中所需涂色最小的一种方案。
• 当子字符串s[l:r]的左边s[l]和右边s[r]不相等时，先继承dp[l][r] = min(dp[l][r - 1], dp[l + 1][r]) + 1作为比较基础。然后又再在l-r之间的寻找子字符串s[l:k]和s[k + 1:r]，由于这两个字符串都比s[l:r]小，所以均已经计算并保存在了计算完的dp中，查表确定大小再与继承值比较，找到其中的最小值方程dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r])
• 最终结果为dp右上角的数值，因为每次循环计算的值都是以对角线顺序填充，最后计算填充的是右上角的值。即s[0:-1]对应的dp[0][-1]填写的值

while True:
    try:
        s = input()
        n = len(s)
        dp = [[0 for _ in range(n)] for _ in range(n)]  # dp[l][r]表示从l字符到r字符涂画所需要的最少次数
        for b in range(n + 1):  # l r之间的相隔步长，从相隔0开始比较，直到相隔n结束
            for l in range(n - b):  # 每次只需要比较到n-b个元素，n - b后面没有步长为b的一对l r
                r = l + b  # 在要比较的l后面相隔b长度提取r
                if b == 0:  # 初始化条件，当1个字符时只有一种涂法
                    dp[l][r] = 1
                elif s[l] == s[r]:  # l和r相等时，dp[l][r]的值是其左边和其下边较小的一个
                    dp[l][r] = min(dp[l + 1][r], dp[l][r - 1])
                else:
                    dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1  # # l和r不相等时，dp[l][r]的值先继承其左边和其下边较小的一个
                    for k in range(l, r):  # 再在l和r之间寻找一个k，使得dp[l][k] + dp[k + 1][r] 最小
                        dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r])
        print(dp[0][-1])
    except:
        break