求解最长公共子序列：动态规划， 子问题分解

求解最长公共子序列：动态规划， 子问题分解

    public String LCS(String str1, String str2){
        if(str1.length() == 0 || str2.length() == 0) return "";
        if(str1.charAt(str1.length() -1) == str2.charAt(str2.length() - 1)){
            return  LCS(str1.substring(0, str1.length()-1), str2.substring(0, str2.length() -1)) + str1.charAt(str1.length() - 1);
        }
        else {
            String result1 = LCS(str1.substring(0, str1.length()), str2.substring(0, str2.length() -1));
            String result2 = LCS(str1.substring(0, str1.length()-1), str2.substring(0, str2.length()));
            if(result1.length() > result2.length()){
                return result1;
            }else {
                return result2;
            }
        }
    }
    @Test
    public void test3(){
        String str1 = "BDCABA";
        String str2 = "ABCBDAB";
        System.out.println(LCS(str1, str2));
    }