题解 | #[CQOI2007]涂色PAINT#

解题思路：

• 根据题目的提示，对于区间$[l,r][l,r]$，令$d{p}_{l,r}dp\_\{l,r\}$表示区间中需要的最少涂色次数，若$colo{r}_l=colo{r}_{r}color\_l\; =\; color\_r$，则$d{p}_{l,r}dp\_\{l,r\}$可以由$d{p}_{l+1,r}dp\_\{l+1,\; r\}$或者$d{p}_{l,r-1}dp\_\{l,r-1\}$转移过来，不会增加涂色次数，因为r或l可以由l或r直接一笔涂色完成。即最少涂色次数可以是:$d{p}_{l,r}=\min (d{p}_{l+1,r},d{p}_{l,r-1}),colo{r}_l=colo{r}_{r}dp\_\{l,r\}\; =\; \backslash min(dp\_\{l+1,r\},\; dp\_\{l,\; r-1\}),\; \backslash \; color\_l\; =\; color\_r$
• 对于区间$[l,r]\mathrm{，}colo{r}_l\mathrm{\ne }colo{r}_r[l,r]，\; color\_l\; \backslash neq\; color\_r$，需要枚举区间中的每一个点有状态转移方程：$d{p}_{l,r}=\min (d{p}_{l,r},d{p}_{l,k}+d{p}_{k+1,r}),k\in [l,r)dp\_\{l,r\}\; =\; \backslash min(dp\_\{l,r\},\; dp\_\{l,k\}+dp\_\{k+1,r\}),k\; \backslash in\; [l,\; r)$
• 初始化$d{p}_{i,i}=1,i\in [0,len)dp\_\{i,i\}\; =\; 1,\; i\; \backslash in\; [0,len)$

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int ln = s.size();
    vector<vector<int>> dp(ln, vector<int>(ln, 0));
    for (int i = 0; i < ln; ++i)
        dp[i][i] = 1;
    for (int len = 2; len <= ln; ++len)
    {
        for (int l = 0; l < ln - 1; ++l)
        {
            int r = l + len - 1;
            if (r >= ln)
                break;
            dp[l][r] = r - l + 1;
            if (s[l] == s[r])
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
            else
            {
                for (int k = l; k < r; ++k)
                {
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
                }
            }
        }
    }
    cout << dp[0][ln - 1] << endl;
    return 0;
}