题解 | #[CQOI2007]涂色PAINT# python简洁版

设置dp数组 dp[left][right] 表示将区间 [left, right] 染色的最少次数。由于可以将连续的区间一次性染完，所以如果 s[left] == s[right] 那么直接由子状态转移而来，否则就分成两段染色。

$dp[left][right]=1,left==right,\mathrm{即}len==1dp[left][right]=min(dp[left+1][right],dp[left][right-1]),ifs[left]==s[right]dp[left][right]=min(dp[left][right],dp[left][mid]+dp[mid+1])ifs[left]!=s[right]andmid\in [left,right)\mathrm{注}\mathrm{意}\mathrm{右}\mathrm{边}\mathrm{取}\mathrm{不}\mathrm{到}dp[left][right]\; =\; 1,\; left\; ==\; right,\; 即\; len\; ==\; 1\; \backslash \backslash \; dp[left][right]\; =\; min(dp[left\; +\; 1][right],\; dp[left][right\; -\; 1]),\; if\; \backslash \; s[left]\; ==\; s[right]\; \backslash \backslash \; dp[left][right]\; =\; min(dp[left][right],\; dp[left][mid]\; +\; dp[mid\; +\; 1])\; \backslash \; if\; \backslash \; s[left]\; !=\; s[right]\backslash \; and\backslash \; mid\backslash in[left,\; right)\; 注意右边取不到$

s = ' ' + input()
# 注意这里需要减一
n = len(s) - 1
dp = [[float("inf")] * (n + 1) for _ in range(n + 1)]

# 遍历所有的长度，注意状态转移方程是从中心开始的
for len in range(1, n + 1):
  	# 所有的左边起点
    for left in range(1, n - len + 2):
        right  = left + len - 1
        if len == 1:
            dp[left][right] = 1
            continue
        if s[left] == s[right]:
            dp[left][right] = min(dp[left + 1][right], dp[left][right - 1])
        else:
            for mid in range(left, right):
                dp[left][right] = min(dp[left][right], dp[left][mid] + dp[mid + 1][right])
print(dp[1][n])