运行结果：
cout<<func1("1aaa1","aaa",0,4,0,2)<<endl; //输出4 cout<<func1("aaa","1aaa1",0,2,0,4)<<endl; //输出6 3.2动态规划法求解递归法易于理解，但是存在对子问题的重复计算，时间效率低下，可以将子问题的结果存储起来，把递归实现，转换为迭代实现，这样就变成了动态规划。递归法是自顶向下，而动态规划是自底向上递归法是需要某个结果时就调用自己来计算，动态规划把每次递推的结果保存在数组中。因为这里有i，ir，j，jr一个4个变量，所以其实需要一个4维数组，这里用了一个宏代替，将4维数组通过下标转变变为一维数组。具体实现参考如下代码：
int func2 (const string &a ,const string &b) { const int la = (int) a.length () ; const int lb = (int) b.length () ; vector<int> ret (la * la * lb * lb) ; #define VRET(a ,b ,c ,d) (ret[(a) * la * lb * lb + (b) * lb * lb + (c) * lb + (d)]) for (int ix = la - 1 ; ix >= 0 ; ix--) for (int irx =ix ; irx < la ; irx++) for (int jx = lb - 1 ; jx >= 0 ; jx--) for (int jrx =jx ; jrx < lb ; jrx++) { int i = ix ; int ir = irx ; int j = jx ; int jr = jrx ; while (i <= ir && j <= jr && a[i] == b[j]) { i++ ; j++ ; } while (i <= ir && j <= jr && a[ir] == b[jr]) { ir-- ; jr-- ; } if (i > ir) { //A为空串 VRET (ix ,irx ,jx ,jrx) = (jr + 1 - j) + 2 ; continue ; } else if (j > jr) { //B为空串 VRET (ix ,irx ,jx ,jrx) = 2 ; continue ; } int tmp = 2 + (jr + 1 - j) + 2 ; //最坏情况，将A全部删除再增加到B for (int k = i + 1 ; k <= ir ; k++) tmp = min (tmp ,2 + VRET (k ,ir ,j ,jr)) ; for (int k = ir - 1 ; k >= i ; k--) tmp = min (tmp ,2 + VRET (i ,k ,j ,jr)) ; for (int k = j + 1 ; k <= jr ; k++) tmp = min (tmp ,(k - j) + 2 + VRET (i ,ir ,k ,jr)); for (int k = jr - 1 ; k >= j ; k--) tmp = min (tmp ,(jr-k) + 2 + VRET (i ,ir ,j ,k)); VRET (ix ,irx ,jx ,jrx) = tmp ; continue ; } return VRET (0 ,la - 1 ,0 ,lb - 1) ; #undef VRET }运行结果：
cout<<func2("dsafsadfadf","fdfd")<<endl; //7 cout<<func2("aaaaaaaa","bbbbbbbb")<<endl; //12