【leetcode】编辑距离

dp方程“

1、初始化；dp[0][i]=i; dp[j][0]=j;

2.dp[i][j]= dp[i-1][j-1](相等)

dp[i-1][j]+1 ,,dp[i][j-1]+1; dp[i-1][j-1] （这个对应是改的况）

注意字符串下标开始位置就OK了

 1 public class Solution {
 2     public int minDistance(String word1, String word2) {
 3         char c1[]=word1.toCharArray();
 4         char c2[]=word2.toCharArray();
 5         int len1=word1.length();
 6         int len2=word2.length();
 7         int dp[][]=new int[len1+1][len2+1];
 8         int i,j;
 9         for(i=0;i<len2+1;i++) dp[0][i]=i;
10         for(j=0;j<len1+1;j++) dp[j][0]=j;
11         for(i=1;i<len1+1;i++)
12         {
13         
14             for( j=1;j<len2+1;j++)
15             {
16                 if(c1[i-1]==c2[j-1]) dp[i][j]=dp[i-1][j-1];
17                 else{
18                     dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
19                     
20                     dp[i][j]=Math.min(dp[i][j],dp[i-1][j-1]+1);
21                     
22                     
23                     
24                 }
25               
26                 
27                 
28                 
29             }
30             
31             
32             
33         }
34         
35         
36         return dp[len1][len2];
37         
38         
39     }
40 }

View Code