描述

给一个长度为$nn$的空字符串，每次选定一个子串染色，问将字符串染成目标颜色的最小次数

思路

• 经典的区间dp的题目，设$dp[i][j]dp[i][j]$表示将区间$[i,j][i,j]$染成目标颜色的最小花费，转移方程为

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int dp[MAXN][MAXN];
char s[MAXN];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        dp[i][i]=1;
    for(int len=2;len<=n;len++)
        for(int i=1;i<=n-len+1;i++)
        {
            if(s[i]==s[i+len-1])
                dp[i][i+len-1]=min(dp[i+1][i+len-1],dp[i][i+len-2]);
            for(int j=i;j<i+len;j++)
                dp[i][i+len-1]=min(dp[i][i+len-1],dp[i][j]+dp[j+1][i+len-1]);
        }
    printf("%d\n",dp[1][n]);
}

时间复杂度$O(n^3)O(n^3)$，空间复杂度$O(n^2)O(n^2)$