涂色PAINT

难度：3星

定义 $dp[i][j]dp[i][j]$ 为 $[i,j][i,j]$ 区间的涂色次数的最小值。那么有3种转移方式：

① $dp[i][j]dp[i][j]$ 由 $dp[i+1][j]dp[i+1][j]$ 转移而来。若 $s[i]==s[i+1]s[i]==s[i+1]$ 或者 $s[i]==s[j]s[i]==s[j]$ 那么不需要额外的次数，否则次数加一。

① $dp[i][j]dp[i][j]$ 由 $dp[i][j-1]dp[i][j-1]$ 转移而来。若 $s[j-1]==s[j]s[j-1]==s[j]$ 或者 $s[i]==s[j]s[i]==s[j]$ 那么不需要额外的次数，否则次数加一。

③ $dp[i][j]dp[i][j]$ 由 $dp[i][k]dp[i][k]$ 和 $dp[k+1][j]dp[k+1][j]$ 转移而来。我们需要枚举每一个 $kk$ 来判断最小值是否更新。

前两个是 $O(1)O(1)$ 的转移，第三个是 $O(n)O(n)$ 的转移， 由于区间的总数为 $n^{2}n^2$ 个，所以总时间复杂度为 $O(n^3)O(n^3)$ 。

#include<bits/stdc++.h>
using namespace std;
int dp[101][101];
int main(){
    string s;
    cin>>s;
    int i,j,n=s.length();
    for(i=1;i<=n;i++){
        for(j=1;j<=n-i+1;j++){
            int l=j,r=j+i-1;
            if(i==1)dp[l][r]=1;
            else{
                int temp1=dp[l+1][r]+1;
                if(s[l-1]==s[r-1]||s[l-1]==s[l])temp1--;
                int temp2=dp[l][r-1]+1;
                if(s[r-1]==s[r-2]||s[r-1]==s[l-1])temp2--;
                dp[l][r]=min(temp1,temp2);
            }
            for(int k=l;k<r;k++)dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
        }
    }
    cout<<dp[1][n];
}