图片说明

  • 对角线上的点都是对应前n个序列的最优解

    class Solution {
  public int minDistance(String word1, String word2) {
      char w1[] = word1.toCharArray();
      char w2[] = word2.toCharArray();
      int n = w1.length;
      int m = w2.length;
      int f[][] = new int [n+1][m+1];
      for(int i = 0 ; i < n ; i++) {
          for(int j = 0 ; j < m ; j++) {
              if(w1[i]==w2[j])
                  f[i+1][j+1] = f[i][j]+1;//Math.max(f[i+1][j+1-1], f[i+1-1][j+1-1])+1;//只能是斜上角 用相邻的话自己的位置算了两次
              else
                  f[i+1][j+1] = Math.max(f[i+1][j+1-1],f[i+1-1][j+1]);

          }
      }
       // for(int i = 0 ; i<=n;i++){
       // for(int j = 0 ; j <= m ;j++){
       //     System.out.print(f[i][j]+" ");
       //    }System.out.println();
       // }
      return (m+n)-2*f[n][m];
  }
}