最长公共子序列，由暴力递归给成动态规划

package 左神题目.dp;
//最长公共子序列 ==>样本对应模型题 ==>最好从后开始算
public class longestCommonSubsequence {
    //1.暴力法
    public static int win1(String s1,String s2){
        if(s1==null||s2==null||s1.length()==0||s2.length()==0){
            return 0;
        }

        char[]  str1 = s1.toCharArray();
        char[]  str2 = s2.toCharArray();
        return process1(str1,str2,str1.length-1,str2.length-1);
    }

    public static int process1(char[] str1,char[] str2,int i,int j){
        if(i==0&&j==0){
            return str1[i]==str2[j]?1:0;
        }else if(i==0){
            //去str2找有没有以i字符结尾的
            return str1[i]==str2[j]?1:process1(str1,str2,i,j-1);
        }else if(j==0){
            //去str1找有没有以j字符结尾的
            return str1[i]==str2[j]?1:process1(str1,str2,i-1,j);
        }else {//i!=0&&j!=0
            //完全不考虑以i结尾，只考虑以j结尾
            int p1 = process1(str1,str2,i-1,j);

            //完全不考虑以j结尾，只考虑以i结尾
            int p2 = process1(str1,str2,i,j-1);

            //同时考虑以i和j结尾
            int p3 = str1[i]==str2[j]? (1+process1(str1,str2,i-1,j-1)):0;

            return Math.max(Math.max(p1,p2),p3);
        }
    }
    //2.动态规划
    //严格表依赖
    public static int win2(String s1,String s2){
        if(s1==null||s2==null||s1.length()==0||s2.length()==0){
            return 0;
        }

        char[]  str1 = s1.toCharArray();
        char[]  str2 = s2.toCharArray();
        int N = str1.length,M = str2.length;
        int[][] dp = new int[N][M];

        //i==0&&j==0 ==> return str1[i]==str2[j]?1:0;
        dp[0][0] = str1[0]==str2[0]? 1:0;

        //i==0 ==>  return str1[i]==str2[j]?1:process1(str1,str2,i,j-1);
        for(int j=1;j<M;j++){
            dp[0][j] = str1[0]==str2[j]?1:dp[0][j-1];
        }

        //j==0 ==> return str1[i]==str2[j]?1:process1(str1,str2,i-1,j);
        for(int i=1;i<N;i++){
            dp[i][0] = str1[i]==str2[0]?1:dp[i-1][0];
        }

        for(int i=1;i<N;i++){
            for(int j=1;j<M;j++){
                // p1 = process1(str1,str2,i-1,j);
                int p1=dp[i-1][j];

                //p2 = process1(str1,str2,i,j-1);
                int p2=dp[i][j-1];

                //int p3 = str1[i]==str2[j]? (1+process1(str1,str2,i-1,j-1)):0;
                int p3= str1[i]==str2[j]? 1+dp[i-1][j-1]:0;

                //return Math.max(Math.max(p1,p2),p3);
                dp[i][j]=Math.max(Math.max(p1,p2),p3);
            }
        }
        return dp[N-1][M-1];
    }
    public static void main(String[] args){
        String s1="1234g1111121";
        String s2="1l2j3j4p1111121";
        long start1 = System.currentTimeMillis();//计算时间
        System.out.println(win1(s1,s2));
        long end1 = System.currentTimeMillis();
        System.out.println("cost time:" + (end1-start1)+"ms");

        long start2 = System.currentTimeMillis();//计算时间
        System.out.println(win2(s1,s2));
        long end2 = System.currentTimeMillis();
        System.out.println("cost time:" + (end2-start2)+"ms");

    }
}