前言

翻遍洛谷题解，看到大家都在套模板，却很少有人讲出为什么，使我十分崇拜天赋哥。

原题链接

关于这题的一些事实性证据

事实1.来自

事实2.来自

事实3.来自

事实4.来自

整理上述事实

1.每一次”最短“最优涂色，要么在其他颜色的基础上涂，这称之为融入一个整体；要么另辟蹊径单独找一块地涂，这称为创立一个整体。
2.任一两端颜色不同的区间，区间内必然存在两个及以上的整体，所以枚举区间内的断点其实就是在找整体与整体之间的分割点。如果断电不在整体间的分割点上，值会多算一部分，就大了；断点无论在哪两个区间的分割点上，其dp和都是一样的。

代码如下

#include<bits/stdc++.h>
using namespace std;
int dp[55][55]={0};
int main()
{
    char s[100];
    cin>>s;

    int n=strlen(s);
    for(int i=0;i<n;i++) dp[i][i]=1;

    for(int k=2;k<=n;k++)
        for(int i=0;i+k-1<n;i++)
        {
            int j=i+k-1;
            if(s[i]==s[j]) dp[i][j]=dp[i][j-1];
            else
            {
                int ans=2e9;
                for(int m=i;m+1<=j;m++)ans=min(ans,dp[i][m]+dp[m+1][j]);
                dp[i][j]=ans;
            }
        }
    cout<<dp[0][n-1];
    return 0;
}