题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2476

解题思路

大思路：
题目要求字符串A转换到字符串B，我们先求空串（即与B串中任意同一位置的字符都不相等的字符串）转换到字符串B最少需要进行多少次操作（此情况为字符串A转换到字符串B的最坏情况，即每个位置对应字符都不相同，但凡A中存在与B同位置字符相等，都不至于操作这么多次），再根据空串转换到B串的操作次数，算出A串转化到B串的操作次数。
S1：空串转换到B串：
本质上是求每一段区间的空串转换成对应区间的B串的最少操作次数，用dp[i][j]保存。
这时候我们考虑，要是B串中能有相同的字符就好了，要是全是不相同的，还得每个字符都转换一下，有相同的就可以少转换几次了，因为可以一次性转换多个空串字符成B串字符。
因此，我们从每个[i,j]区间找k，满足B串中i位置与B串中k位置字符相等，此条件满足时，刷新dp[i][j]的值， dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]。
为什么是dp[i+1][k]+dp[k+1][j]？
dp[i+1][k]表示将空串区间[i+1,k]转换为B串区间[i+1,k]最少操作次数，dp[k+1][j]表示将空串区间[k+1,j]转换为B串区间[k+1,j]最少操作次数。此时满足的条件为 B[i]==B[k]，由于修改空串k位置字符的操作同时也修改了空串i位置字符，因此，只要加上了修改k位置的这一次操作，就不应该再加上修改i位置的操作了。
之后就是不停的找k，满足条件刷新dp。
S2：A串转换到B串：
空串转换成B串与A串转换成B串的最少操作次数只差在有的位置A串与B串相等，可能无需修改，而这些A串B串字符位置的位置，空串与B串并不相等，必须修改，这就是他俩之间操作次数差异产生的原因，同时也为求解A串转化为B串最少次数提供了思路。
这么看来我们还得刷新一遍，这次刷新我们不用枚举区间长度，区间左端点，再枚举个k。这次只要固定区间左端点为字符串最左端就行，枚举右端点去刷新从最左端到某位置由A串转化为B串的最少操作次数。
我们用ans[0][i]表示区间[0,i]将A串转化为B串最少修改次数。
假如同一位置上，A串字符与B串字符相等，我们完全可以不去修改此位置的字符啊，所以此时区间修改的最少次数就等于前一个区间的修改次数，即 ans[0][i]=ans[0][i-1]；但是，如果不相等，我们就只能尝试着去找一个k，使得区间[0,k]的最少修改次数+区间[k+1,i]的最少修改次数的最小可能作为区间[0,i]的最少修改次数。
这么一想，这和已经求出的dp[0][i]不一样嘛，直接用多香啊！停停停！不一样好吧！你看看上面那步， ans[0][i]=ans[0][i-1]，这说明我们可能已经对区间[0,i]的最少修改次数进行了刷新，而你又拿着老版的dp当最少修改次数，是不是说不过去了。
所以，我们得用ans去刷新ans的值，就有了转移方程 ans[0][i]=min(ans[0][i],ans[0][k]+ans[k+1][i]
停停停！又有个问题，这 ans[k+1][i]我们也没求过啊！对，我们没求过，但是我们求过 dp[k+1][i]啊，虽然dp[0][k]被刷新过（其实并非dp被刷新，本质是dp未变，而是用ans存下了新的dp值）但是dp[k+1][i]没被刷新过吧，所以照用不误，转移方程 ans[0][i]=min(ans[0][i],ans[0][k]+dp[k+1][i]。又因为ans数组的第一维完全没有用到，所以简化成一维数组ans[i]表示前i个位置（含i）最少修改次数，下面代码就是如此体现的。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,dp[N][N],ans[N];
string a,b;
int main(){
    while(cin>>a>>b){
        int n=a.size();
        a='.'+a;
        b='.'+b;
        memset(dp,0,sizeof dp);
        memset(ans,0,sizeof ans);
        for(int i=1;i<=n;i++) dp[i][i]=1;//对于空串而言，每个位置修改一次成为B串

        //S1
        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                dp[i][j]=dp[i+1][j]+1;//省一次额外的遍历，在此进行赋初值操作
                for(int k=i+1;k<=j;k++)//注意遍历范围，因为i要与比i大的全部点判等 
                    if(b[i]==b[k]) 
                        dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);                    
            }

        //S2
        for(int i=1;i<=n;i++) ans[i]=dp[1][i];//对ans初始化！
        for(int i=1;i<=n;i++)
            if(a[i]==b[i]) ans[i]=ans[i-1];
            else for(int k=1;k<i;k++) ans[i]=min(ans[i],ans[k]+dp[k+1][i]);

        cout<<ans[n]<<endl;
    }
}

总结

确实挺难理解的，看了好多题解，他们讲的也不清楚，加上我也笨，看了一晚上，到现在写完题解已经是半夜1：16了，希望对大家和自己能有所帮助！