动态规划算法通常基于递推公式和一个或多个的初始状态。目前存在的问题的解决方案将会提出的问题的解关于。用动态规划法解决需要只多项式复杂性，所以它是多个

回溯，暴力快速的方法。首先，我们需要找到一个最佳的解决方案，然后与帮助下，找到下一个状态的最优解。做是抽象的动态规划方程的状态和状态转换 (递推公式)。

第二，编辑距离

1，问题的描述
让和 b 为 2 的字符串。与最小 b 操作将字符串转换为一个字符的字符串。这里的字符操作包括:

(1) 删除一个字符;
(2) 插入字符;
(3) 到一个字符更改为另一个字符。
将转换为字符串的最少字符数操作数作为字符串编辑距离，字符串 b 到 b，记为 d (a，b)。尝试设计一种高效算法对于任何给定的 2 字符串和 b，计算其编辑距离 d (a，b)。
要求:
输入: 第 1 行是一个字符串，第二行是字符串 b。
输出: 字符串编辑距离 d 和 b (a、 b)

2，求解过程

用 d [i，j] A [1…我] B [1…j] 编辑距离

D [i，0] = i: 表明该字符串为空字符串的长度，我编辑是长度的距离;

D [0，j] = j: 代表到字符串长度 j b 编辑距离的空字符串的长度是字符串 b;

d [i，j] = d [i-1，j-1]: 如果 [i] = = B [j];

D [i，j] = min (d [i-1，j-1] ([i] 替换 B[j])，d [i-1，j] ([i] 删除)，d [i，j-1] ([i] 后 B[j])) + 如果插入 [i]!= B [j]。

Java 代码:

public class EditDistance {
 int min(int a,int b,int c) {  
     int t = a < b ? a : b;  
     return t < c ? t : c;  
 }  
 void editDistance(char[] s1,char[] s2) {
  int len1=s1.length;
  int len2=s2.length;
     int d[][]=new int[len1+1][len2+1];  
     int i,j;  
     for(i = 0;i <= len1;i++)  
         d[i][0] = i;  
     for(j = 0;j <= len2;j++)  
         d[0][j] = j;  
     for(i = 1;i <= len1;i++)  
         for(j = 1;j <= len2;j++)
         { 
             int cost = s1[i-1] == s2[j-1] ? 0 : 1;  
             int deletion = d[i-1][j] + 1;  
             int insertion = d[i][j-1] + 1;  
             int substitution = d[i-1][j-1] + cost;  
             d[i][j] = min(deletion,insertion,substitution);  
         }
     System.out.println(d[len1][len2]);
 }
 public static void main(String[] args)
 {
    EditDistance ed = new EditDistance();
    String a="abd";
    String b="bcd";
    ed.editDistance(a.toCharArray(),b.toCharArray());
 }

}