LA 4394 刷字符串（区间dp）

小鱼儿 2021-11-16 16:58 239阅读 0赞

## 题意：给定两个长度相等，只有小写字母组成字符串A和B，每步可以把A的一个连续子串刷成同一个字母，问至少需要多少步才能把A变成B。 ##

## 分析：区间DP，区间DP的套路就是 d\[i\]\[j\]的在区间 (i,j) 刷的次数。二维无法转移，所以需要增加维度。关键是贪心出一个性质，每次刷一个串，都可以从头开始刷起，如果第一个字符相同，则从第二个开始刷，而每次刷要么只刷一个字符，要么刷到另一个与目标串首字符相同的字符为止。dp\[L\]\[R\]\[C\]表示将该串刷成目标串所需要的最小步数（L、R表示待刷的字符串的区间，C表示该字符串的状态，如果C为26则表示该串未被刷，而当0<=C<=25时，则表示该串被刷成了’a’+C-1的字符序列）。状态转移方程为dp\[L\]\[R\]\[C\]=min\{1+dp\[L+1\]\[k-1\]\[s2\[L\]-‘a’+1\]+dp\[k+1\]\[R\]\[C\]  | s2\[L\]==s2\[k\]\}，边界条件为当L>R时，dp值为0。参考[http://www.bubuko.com/infodetail-2777944.html][http_www.bubuko.com_infodetail-2777944.html]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    char str1[1000],str2[1000];
    int dp[160][160][36];
    ///记忆化搜索
    int dfs(int l,int r,int c){
        if(l>r)///边界
            return 0;
        if(dp[l][r][c]!=-1)
            return dp[l][r][c];
        if((c==26&&str1[l]==str2[l])||str2[l]==c+'a')
            return dp[l][r][c]=dfs(l+1,r,c);
        dp[l][r][c]=1+dfs(l+1,r,c);
        for(int i=l+1; i<=r; i++)
            if(str2[l]==str2[i])
                dp[l][r][c]=min(dp[l][r][c],1+dfs(l+1,i-1,str2[l]-'a')+dfs(i+1,r,c));
        return dp[l][r][c];
    }
    int main(){
        while(~scanf("%s%s",str1,str2)){
            int len=strlen(str1);
            memset(dp,-1,sizeof(dp));
            printf("%d\n",dfs(0,len-1,26));
        }
        return 0;
    }

[http_www.bubuko.com_infodetail-2777944.html]: http://www.bubuko.com/infodetail-2777944.html