求两个字符串的最长公共子序列

动态规划法求解两个字符串的最长公共子序列。

https://www.cnblogs.com/hapjin/p/5572483.html

import java.util.*;

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        int [][] curr = new int [n+1][m+1];
        for (int i =0; i <= n; i++) {
            curr[i][0] =  0;
        }
        for (int j =0; j <= m; j++) {
            curr[0][j] =  0;
        }
        for(int p = 1; p <= n; p++){
            for(int q = 1; q <= m; q++){
                if(A.charAt(p-1) == B.charAt(q-1)) {
                    curr[p][q] = curr[p-1][q-1]+1;
                }else if(curr[p][q-1] > curr[p-1][q]){
                    curr[p][q] = curr[p][q-1];
                }else {
                    curr[p][q] = curr[p-1][q];
                }
            }
        }
        return curr[n][m];
    }
}