本文共 3160 字，大约阅读时间需要 10 分钟。

题意：给定两个字符串a,b，长度相等且不超过100。每次可以将a的一个子串改为江铜字符组成的子串，问最少多少次能将a变为b

题解：这题稍微有点难了emm

• 大佬题解：先不考虑a，dp[i][j]先表示将一个空串转化为b[i~j]的最小操作；然后再考虑a的影响，如果a[k]==b[k]，dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j])。

总结：重点是分成两步解决

代码：

大佬代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 105;int dp[N][N];char a[N], b[N];int main() {    while (~scanf("%s", a + 1)) {        scanf("%s", b + 1);        int n = strlen(b + 1);        //将空串填成b        for (int i = n; i >= 1; --i) {            for (int j = i; j <= n; ++j) {                dp[i][j] = j - i + 1;                for (int k = i; k + 1 <= j; ++k) {                    if (b[i] == b[k + 1])                        dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);                    //更新k+1的时候就整段覆盖了i+1~k再自行解决                    else                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);                }            }        }        // cout << dp[1][n] << endl;        //再在b的基础上考虑a的影响        for (int i = n; i >= 1; --i) {            for (int j = i; j <= n; ++j) {                for (int k = i; k <= j; ++k) {                    if (a[k] == b[k])                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j]);                }            }        }        printf("%d\n", dp[1][n]);    }    return 0;}
       
      
     
    
   

转化成我的代码：

• 第一步（不考虑a）的操作不一样，我认为区间dp都可以小区间->大区间的更新方式（上面大佬并不是，我试了试，果然也ok）
• 第二部（考虑a）的操作一样，因为第二步很明显只需要在更新dp[i][j]的时候将所有的dp[i][i~j-1],dp[i-1~j][j]更新了就ok了（实际上也是可以小区间->大区间的）
• 注意：表示的是在更新区间dp[i][k]的时候可以顺便把b[k~n]更新为b[k]（同理也可以同时更新b[1~i-1]为b[i]），然后k+1~j-1区间取最小操作数即可（该区间自行操作）。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        // #define int long longusing namespace std;const int N = 1e2 + 10;const int INF = 1e9;  //最大不超过1e8int n, dp[N][N];char a[N], b[N];signed main() {    while (scanf("%s%s", a + 1, b + 1) != EOF) {        n = strlen(a + 1);        int len, i, j, k;        for (i = 1; i <= n; i++) dp[i][i] = 1;        for (len = 2; len <= n; len++) {            for (i = 1; i + len - 1 <= n; i++) {                j = i + len - 1;                if (b[j] == b[j - 1])                    dp[i][j] = dp[i][j - 1];                else                    dp[i][j] = dp[i][j - 1] + 1;                for (k = i; k < j; k++) {                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);                    if (b[k] == b[j])                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1]);                }            }        }        // for (i = 1; i <= n; i++) {        // for (j = 1; j <= n; j++) {        // if (dp[i][j] == INF) dp[i][j] = -1;        // printf("%3d ", dp[i][j]);        // }        // cout << endl;        // }        for (i = 1; i <= n; i++) {            for (j = i; j <= n; j++) {                for (k = i; k <= j; k++) {                    if (a[k] == b[k])                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j]);                }            }        }        cout << dp[1][n] << endl;    }    return 0;}/*inpput:::zzzzzfzzzzzabcdefedcbaababababababcdcdcdcdcdcdoutput:::67*/
       
      
     
    
   

转载地址：https://blog.csdn.net/I_have_a_world/article/details/117668773 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！