最长公共子序列/数组

最长公共子数组

• 公共子串长度问题。

• 要连续的，而非断续

• 代码

  class Solution {
   public int findLength(int[] A, int[] B) {
        int n = A.length;
        int m = B.length;
        int f[][] = new int [n+1][m+1];
        int ans = 0 ;
        for(int i = 0; i < n ; i++) {  //最长公共子数组
            for(int j = 0 ; j < m ; j++) {
                if(A[i]==B[j]) {
                    f[i+1][j+1] =  f[i][j]+1;//只能由斜上角的值决定
                }
                else {
                    f[i+1][j+1] = 0;  //本想传递给下一个 结果发现传递反而影响结果
                }
                ans = Math.max(ans,f[i+1][j+1]);
            }
  
        }
       // for(int i = 1 ; i<=n;i++){
       //     for(int j = 1 ; j <= m ;j++){
       //         System.out.print(f[i][j]+" ");
       //     }System.out.println();
       // }
        return ans;
  
    }
  }

最长公共子序列

 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];
    }
}