一、题意：给定一个长度最多为50的串S，求用最少的步数将S变成由两个相同的串连接而成的，所用的方法可以是(假设原始串S为aaba)：
1、删除串中一个特定字符,eg.aaba-->aba；
2、在串S的任意的位置添加一个字符,eg.aaba-->aabba；
3、修改串S的任意一个字符，eg.aaba-->aaaa；
题外话：由于省赛的时候见过此类字符串最少修改次数的题目，当时不会做，大牛说是用构造图，然后bfs完成的。当然那题与此题不相同。
二、分析：由于串S的最终是要变成两个相同子串的拼接，因此，我们可以将S分割成两个子串s1和s2，通过dp来获得最少修改步数使得两个子串相等，通过枚举在串S上的分割点得到当前状态对应的最少修改步数，从而获得全局的最少修改步数。
dp[i][j]表示s1长度为i，s2长度为j，s1和s2相同最少需要的修改的步数
1、当s1[i]==s1[j]的时候，我们不需要修改任何字符；
2、当s1[i]!=s2[j]时，我们可以有五种方法处理：
2-1、在s1[i]位置插入一个s2[j]字符，来达到这两个位置对应的字符相等，此时需要需要一步修改，即dp[i][j]=dp[i-1][j]+1;
2-2、在s2[j]位置插入一个s1[i]字符，此时同样需要一步修改，即dp[i][j]=dp[i][j-1]+1；
2-3、把s1[i]位置的字符删除掉，此时新得到的状态相当于由dp[i][j-1]状态转变过来，即dp[i][j]=dp[i][j-1]+1;
2-4、把s2[j]位置的字符删除掉，即dp[i][j]=dp[i-1][j]+1;
2-5、把s1[i]位置的字符修改成s2[j]位置对应的字符或者反过来，此时相当于从状态dp[i-1][j-1]转变过来，即dp[i][j]=dp[i- 1][j-1]+1;
因此得到的状态方程为：
|-----dp[i-1][j-1];.................................................(s1[i]==s2[j])
dp[i][j]=|
|-----min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;........(s1[i]!=s2[j])
串s1（长度len1）,串s2（长度len2）对应的最少修改步数为dp[len1][len2]。
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; #define min(a,b) ((a)<(b)?(a):(b)) class MakeSquare { public: string s; int len; int f[55][55]; int minChanges(string); int GetMin(int limit){ int i,j; int len2=len-limit; //init memset(f,0,sizeof(f)); for(i=0;i<=limit;++i) f[i][0]=i; for(i=0;i<=len2;++i) f[0][i]=i; for(i=1;i<=limit;++i) for(j=1;j<=len2;++j) { if(s[i-1]==s[limit+j-1]) f[i][j]=f[i-1][j-1]; else f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1; } return f[limit][len2]; } }; int MakeSquare::minChanges(string S) { s=S; len=S.length(); int ans=len; for(int i=0;i<len;++i) {//splite string S to s1 ,s2 to get the min_step ans=min(ans,GetMin(i)); } return ans; }
菜鸟毕竟是菜鸟，刚看到RoBa用了相当少的时间就搞定了此题。
