【算法&数据结构体系篇class19】：暴力递归到记忆化搜索到动态规划

我就是我 2024-03-25 22:34 51阅读 0赞

### 一、背包问题 ###

> 给定两个长度都为N的数组weights和values，  
> weights\[i\]和values\[i\]分别代表 i号物品的重量和价值。  
> 给定一个正数bag，表示一个载重bag的袋子，  
> 你装的物品不能超过这个重量。  
> 返回你能装下最多的价值是多少?

package class19;
    
    /** 背包问题
     *
     * 给定两个长度都为N的数组weights和values，
     * weights[i]和values[i]分别代表 i号物品的重量和价值。
     * 给定一个正数bag，表示一个载重bag的袋子，
     * 你装的物品不能超过这个重量。
     * 返回你能装下最多的价值是多少?
     *
     * 思路： 暴力递归 再将逻辑条件转换成缓存表 得到 最终动态规划解法
     */
    public class Knapsack {
        // 所有的货，重量和价值，都在w和v数组里
        // 为了方便，其中没有负数
        // bag背包容量，不能超过这个载重
        // 返回：不超重的情况下，能够得到的最大价值
    
        //方法一 暴力递归
        public static int maxValue(int[] w, int[] v, int bag) {
            //边界判断 重量和价值空或者长度0，或者两个数组长度不相等 就是异常输入 直接返回0
            if(w == null || w.length == 0 || v == null || v.length == 0 || w.length != v.length){
                return 0;
            }
            //调用暴力递归函数 尝试
            return process(w,v,0,bag);
        }
    
        /**
         *
         * @param w     当前的权重数组
         * @param v     当前的价值数组
         * @param index 当前所来到的位置
         * @param bag   当前所剩余的背包容量
         * @return      返回不超容量情况下，能得到的最大价值
         * 一开始就是从数组0 首个位置开始往右遍历
         */
        public static int process(int[] w, int[] v, int index, int bag){
            if(bag < 0){
                //base case:如果背包容量当前是小于0了 说明是前一次 取的重量w 已然大于剩余容量bag 所以要返回上层调用-1 说明上层操作时无效操作 不能取，
                // 为什么=0不用处理，因为题意所说的没有负数而已 可能存在某个位置 权重0 价值大于0  所以bag0 也是可以取的
                return -1;
            }
            if(index == w.length){
                return 0;   //base case:索引位置 越界了  那么就直接返回0 表示没有元素可取了
            }
            //接着判断情况，当前索引位置可取 与 不可取
            int p1 = process(w,v,index+1,bag);  //不取，index位置下移，bag容量不变
    
            //取， index下移，bag容量要减去w[index]权重值 不过这里还需要判断，是否是可取的，比如w[0]= 6 v[0]=1 bag=5 长度1的数组 此时需要判断5<6不能取，所以我们base case做了判断 不能取返回-1
            int p2 = 0; //先初始化0 根据是否前面可取再加上 v价值
            //先取出后是否不满足 做个判断
            int rest = process(w,v,index+1,bag - w[index]);
            //如果不等于-1 说明是可取的
            if(rest != -1){
                p2 = v[index] + rest;  //将当前位置价值累加起来
            }
            return Math.max(p1,p2);   //最后返回两者情况较大者
        }
    
        //方法二 动态规划
        public static int dp(int[] w, int[] v, int bag){
            //边界判断 重量和价值空或者长度0，或者两个数组长度不相等 就是异常输入 直接返回0
            if(w == null || w.length == 0 || v == null || v.length == 0 || w.length != v.length){
                return 0;
            }
            //根据递归函数影响参数是索引index 以及背包容量bag 定义范围 index就是数组范围0,N-1 遍历过程会到w.length越界处，所以是0,N   bag一开始最大值是bag开始容量，遍历过程可能会减到负数 范围是 负数，bag
            //我们就直接定义正数边界
            int N = w.length;
            int[][] dp = new int[N+1][bag+1];
            //根据递归函数边界判断 index == w.length 返回0 表示dp[N-1][] 最后一行都是0 因为初始化数组值都是0 所以不用处理
            //bag<0 返回-1 负数边界子啊二维数组左侧 我们不需要去处理 跳过
    
            //接着判断情况，当前索引位置可取 与 不可取 都是与index+1依赖，也就是当前行位置依赖与下一行的位置，所以我们填充数组可以从下往上，
            //已知最后一行是值都为0，所以接着取倒数第二行，每行都从左往右去填充，根据递归函数的尝试逻辑 照着改
            for(int index = N-1; index >= 0;index--){
                for(int restBag = 0; restBag <= bag; restBag++){
                    //从倒数第二行，每行从左往右 index 行   restBag列
                    //第一种情况 不取元素 依赖下一行元素
                    int p1 = dp[index+1][restBag];
                    //第二种情况
                    int p2 = 0; //先初始化0 根据是否前面可取再加上 v价值
                    // 取元素，且判断 取后是否容量小于0 小于0 则返回-1 否则就是依赖index+1  容量减去该位置权重
                    int rest = restBag - w[index] < 0 ? -1 : dp[index+1][restBag-w[index]];
                    if(rest != -1){
                        //如果不等于-1 说明是可取的
                        p2 = v[index] + rest;
                    }
                    dp[index][restBag] = Math.max(p1,p2);   //给表当前位置赋值 较大的情况值
                }
            }
            return dp[0][bag];  //根据递归函数调用 的输入是 索引0 起始背包容量bag 所以转换到表中对应该位置的值就是最大价值
        }
    
        public static void main(String[] args) {
            int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
            int[] values = { 5, 6, 3, 19, 12, 4, 2 };
            int bag = 15;
            System.out.println(maxValue(weights, values, bag));
            System.out.println(dp(weights, values, bag));
        }
    
    }

### 二、数字转换字母的转化次数 ###

> 规定1和A对应、2和B对应、3和C对应...26和Z对应  
> 那么一个数字字符串比如"111”就可以转化为:  
> "AAA"、"KA"和"AK"  
> 给定一个只有数字字符组成的字符串str，返回有多少种转化结果

package class19;
    
    /**
     * 规定1和A对应、2和B对应、3和C对应...26和Z对应
     * 那么一个数字字符串比如"111”就可以转化为:
     * "AAA"、"KA"和"AK"
     * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
     */
    public class ConvertToLetterString {
        // str只含有数字字符0~9
        // 返回多少种转化方案
    
        //方法一 ：暴力递归
        public static int number(String str) {
            //边界判断
            if (str == null || str.length() == 0) return 0;
            //调用递归函数， 从左往右遍历字符数组，返回能转换的方案数
            char[] chars = str.toCharArray();
            return process(chars, 0);
        }
    
        /**
         * @param chars 当前目标字符数组
         * @param index 当前位置chars[0...index-1]已经遍历完 来到chars[index,....]往后的遍历
         * @return 返回能转换的方案数
         */
        public static int process(char[] chars, int index) {
            //base case: 如果索引递归后来到了越界char.length位置 那么就说明前面的都符合转换，返回1次 给上层调用
            if (index == chars.length) return 1;
            //base case:如果没有走到 然后来到一个数字0，说明前面选择是无效的 没有一个0对应的字母 需要返回0 表示前面选择的方案是无效的
            if (chars[index] == '0') return 0;
            //如果还没走完，那么就进行分情况判断
            //情况1 假设当前索引位置chars[index] 单独作为字母转换 依次以每个位置作为一个字母
            int way = process(chars, index + 1);
    
            //情况2 假设index 和index+1 一起做一个转换字母 所以不越界。 已知a-z有26个 对应的数值就是有2位 所以假设符合小于27那么就该情况可行 将情况一的次数加上
            if (index + 1 != chars.length && (chars[index] - '0') * 10 + (chars[index + 1] - '0') < 27) {
                way += process(chars, index + 2);  //这里index ,index+1 已经访问 所以跳过index+1 来到index+2
            }
            return way;
        }
    
    
        //方法二： 动态规划
        //根据暴力递归得知 相关参数1个index 对应一维数组表 进行填充 返回dp[0]
        public static int dp1(String str) {
            //边界判断
            if (str == null || str.length() == 0) return 0;
    
            //定义一维数组表 存放每个情况的值 相关参数index 从方法一中看到index能递归到str的长度 也就是0,N  所以建立N+1长度的数组 索引才能到N
            char[] chars = str.toCharArray();
            int N = chars.length;
            int[] dp = new int[N + 1];
    
            //base case 索引在越界是 值为1 对应N位置值=1
            dp[N] = 1;
    
            //接着补全内容 根据情况分析 index 依赖 index+1 而目前我们已经拿到了N 最后一个位置的值，所以可以从右向左遍历 赋值 N-1 依赖N  N-2依赖N-1...
            for (int index = N - 1; index >= 0; index--) {
                //前面base case还分析到 如果对应得到一个‘0’字符 那表示前面的选择都是无效的赋值0 而数组初始化就是0 无需处理 只有当index 位置的字符不是‘0’ 我们再来分析情况赋值
                if (chars[index] != '0') {
    
                    //情况1 取当前字符作为单独字母 index 依赖 index+1
                    int way = dp[index + 1];
    
                    //情况2 如果index 和 index+1 不越界且符合字母对应数小于27 那么就可以合并两位置作为一个字母
                    if (index + 1 != chars.length && (chars[index] - '0') * 10 + (chars[index + 1] - '0') < 27) {
                        way += dp[index + 2];  //这里index ,index+1 已经访问 所以跳过index+1 来到index+2
                    }
                    //最后将分析情况后的次数 赋值给dp[index]
                    dp[index] = way;
                }
            }
            return dp[0];
        }
    
        // 从左往右的动态规划
        // dp[i]表示：str[0...i]有多少种转化方式
        public static int dp2(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            char[] str = s.toCharArray();
            int N = str.length;
            if (str[0] == '0') {
                return 0;
            }
            int[] dp = new int[N];
            dp[0] = 1;
            for (int i = 1; i < N; i++) {
                if (str[i] == '0') {
                    // 如果此时str[i]=='0'，那么他是一定要拉前一个字符(i-1的字符)一起拼的，
                    // 那么就要求前一个字符，不能也是‘0’，否则拼不了。
                    // 前一个字符不是‘0’就够了嘛？不够，还得要求拼完了要么是10，要么是20，如果更大的话，拼不了。
                    // 这就够了嘛？还不够，你们拼完了，还得要求str[0...i-2]真的可以被分解！
                    // 如果str[0...i-2]都不存在分解方案，那i和i-1拼成了也不行，因为之前的搞定不了。
                    if (str[i - 1] == '0' || str[i - 1] > '2' || (i - 2 >= 0 && dp[i - 2] == 0)) {
                        return 0;
                    } else {
                        dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
                    }
                } else {
                    dp[i] = dp[i - 1];
                    if (str[i - 1] != '0' && (str[i - 1] - '0') * 10 + str[i] - '0' <= 26) {
                        dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
                    }
                }
            }
            return dp[N - 1];
        }
    
        // 为了测试
        public static String randomString(int len) {
            char[] str = new char[len];
            for (int i = 0; i < len; i++) {
                str[i] = (char) ((int) (Math.random() * 10) + '0');
            }
            return String.valueOf(str);
        }
    
        // 为了测试
        public static void main(String[] args) {
            int N = 30;
            int testTime = 1000000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int len = (int) (Math.random() * N);
                String s = randomString(len);
                int ans0 = number(s);
                int ans1 = dp1(s);
                int ans2 = dp2(s);
                if (ans0 != ans1 || ans0 != ans2) {
                    System.out.println(s);
                    System.out.println(ans0);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println("Oops!");
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }

### 三、字符串贴纸拼接得到目标字符串所需的最少贴纸数 ###

> 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文  
> arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来  
> 返回需要至少多少张贴纸可以完成这个任务。  
> 例子：str= "babac"，arr = \{"ba","c","abcd"\}  
> ba+ ba + c 3 abcd+ abcd 2 abcd+ba 2  
> 所以返回2

package class19;
    
    import sun.security.krb5.internal.Ticket;
    
    import java.util.HashMap;
    
    /**
     * 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
     * arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
     * 返回需要至少多少张贴纸可以完成这个任务。
     * 例子：str= "babac"，arr = {"ba","c","abcd"}
     * ba + ba + c  3  abcd + abcd 2  abcd+ba 2
     * 所以返回2
     */
    // 本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
    public class StickersToSpellWord {
        //方法一：递归 不优化 会超时
        public static int minStickers1(String[] stickers, String target) {
            int ans = process1(stickers, target);
            return ans == Integer.MAX_VALUE ? -1 : ans;
        }
    
        /**
         * 递归函数
         *
         * @param stickers 贴纸字符数组
         * @param target   贴纸需要拼接成的目标字符
         * @return
         */
        public static int process1(String[] stickers, String target) {
            //base case: 如果拼接的字符target已经减到0了 说明不需要再贴纸了 返回0
            if (target.length() == 0) return 0;
    
            int min = Integer.MAX_VALUE;  //初始化 贴纸数，默认最大。因为可能不存在能拼接出目标值的结果 那么返回最大值
            //如果没有减到0 那么就进行分情况
            //贴纸数组有多种贴纸字符串，我们依次遍历 每一个都取出来作为第一个遍历拼接
            for (String sticker : stickers) {
                String rest = minus(target, sticker);  //每次取每个贴纸做第一个尝试 然后减去贴纸字符串
                if (target.length() != rest.length()) {
                    //只有减完贴纸后 字符串比原目标字符串短了 也就是不相等了 才说明该贴纸有效，可以选择 否则就不进行下层递归
                    //接着递归，取每次的较小贴纸数。 传递的目标值此时来到 rest 已经减去了第一个贴纸了
                    min = Math.min(min, process1(stickers, rest));
                }
            }
            //最后返回 下层的贴纸最少数，process1(stickers,rest)不包含第一张贴纸 rest已经减去第一个贴纸 所以 最后返回min是下层的贴纸数
            //如果不是最大值，也就是下层有能拼接出目标字符串的贴纸 就不会为最大值 那么就返回min+1 把第一张贴纸数加上
            //如果min=最大值，说明不存在能拼接出的字符串贴纸 返回min+0 最后主程序调用 最大值就是无效
            return min + (min == Integer.MAX_VALUE ? 0 : 1);
        }
    
        //将目标target 字符串减去 sticker贴纸字符串 比如 aabbc   abc  最后返回ab
        public static String minus(String target, String sticker) {
            char[] chars1 = target.toCharArray();
            char[] chars2 = sticker.toCharArray();
            int[] counts = new int[26];  //定义一个数组 计算每个字母的次数 有26个字母
            StringBuilder ans = new StringBuilder();  //字符串接收减完后剩余的字符串
            for (char ch : chars1) {
                counts[ch - 'a']++;  //取出目标字母 依次转换累加到counts 比如aabbc counts[0] 对应a  =2， counts[1] = 2 counts[2] = 1
            }
            for (char ch : chars2) {
                counts[ch - 'a']--; //目标字母都累加到counts了 接下来就将贴纸字符依次对应的位置-- ，最后剩下的counts大于0的位置 的字母就是剩下的字母 再拼接成字符串返回
            }
            for (int i = 0; i < 26; i++) {
                //遍历counts计数数组 如果位置大于0 说明减完之后该字母还有 就需要添加到返回的字符串
                if (counts[i] > 0) {
                    //需要遍历counts[i]次 表示有几个字母 比如counts[0]=2 说明有两个字母a 追加到字符串
                    for (int j = 0; j < counts[i]; j++) {
                        ans.append((char) (i + 'a'));  //索引加a字符 转换字符类型 表示a-z i=0 0+'a'=a 1+'a' = b
                    }
                }
            }
            return ans.toString();
        }
    
    
        //方法二： 递归，进行两个关键：优化1 字符串的字符统计先转换好 优化2 遍历剪枝 遍历有目标首字母的贴纸 还是会超时，需要再加上缓存表记忆化搜索
        public static int minStickers2(String[] stickers, String target) {
            //先将贴纸数组 转换成二维数组 N行 每一个行有26列 每一行就表示一个贴纸 对应的字母在对应行的索引+1
            int N = stickers.length;
            //优化1 词频二维数组代替了贴纸数组 提高效率
            int[][] counts = new int[N][26];   //N行26列 每一行是一个贴纸 对应的26个字母 a对应0  b对应1  第一个，aab字符则表示在counts[0][0]=2 counts[0][1]=1
            for (int i = 0; i < N; i++) {
                //取出每个贴纸字符串转换成字符数组
                char[] ch = stickers[i].toCharArray();
                //依次将每个字符 累计加到count[i]这个贴纸的对应位置c-'a' 累加
                for (char c : ch) {
                    counts[i][c - 'a']++;
                }
            }
            //调用递归函数，传递已经处理好的词频数组和目标字符串
            int ans = process2(counts, target);
            //返回结果 如果是最大值说明没有符合的结果返回-1 否则就是返回ans自身
            return ans == Integer.MAX_VALUE ? -1 : ans;
        }
    
        //优化版本的递归函数
        public static int process2(int[][] stickers, String target) {
            //base case: 目标字符串长度减少到0 说明不需要在匹配了 返回0
            if (target.length() == 0) return 0;
    
            //关键优化1 将目标值也转换成词频数组 方便对比,定义一个26长度数组
            char[] t = target.toCharArray();
            int[] tcounts = new int[26];
            for (char ch : t) {
                tcounts[ch - 'a']++;
            }
    
            //定义一个最小值 用来返回结果
            int min = Integer.MAX_VALUE;
            //开始遍历 counts 贴纸词频数组
            for (int i = 0; i < stickers.length; i++) {
                int[] sticker = stickers[i];  //取出每个贴纸词频数组
    
                //关键优化2 剪枝，也是贪心  按照目标字符串的首字母，如果贴纸字符串是存在该首字母的那么就可以遍历获取
                if (sticker[t[0] - 'a'] > 0) {
                    //定义一个字符串 接收 目标值减去贴纸剩下的字符串
                    StringBuilder str = new StringBuilder();
                    for (int j = 0; j < 26; j++) {
                        if (tcounts[j] > 0) {
                            //开始遍历 词频数组 长度26 如果所在位置大于0 说明目标字符串有该字母 就拿出来跟贴纸进行比较相减7
                            int num = tcounts[j] - sticker[j];  //相同位置相加，剩下的就是剩余的字符串
                            for (int k = 0; k < num; k++) {
                                str.append((char) (j + 'a')); //如果num是大于0的那么就遍历是多少个就累加起来 字母就用 索引j+'a'转换成对应字母
                            }
                        }
    
                    }
                    //当前贴纸减完之后 剩下rest字符串 接着递归 取最小值返回
                    String rest = str.toString();
                    min = Math.min(min, process2(stickers, rest));
                }
            }
            //最后返回min上层最小值 如果说min是最大值说明不存在这个符合情况返回0 否则返回1
            return min + (min == Integer.MAX_VALUE ? 0 : 1);
        }
    
        //方法三： 最佳优化：添加缓存表 记忆化搜索  因为这个字符串类型不像整形 很难定义一个边界进行动态规划优化 所以做到极致优化 就是记忆化搜索 因为存在由重复子问题
        //比如两个贴纸减完之后 剩余的字符串值相同 那么就可以将值保存在哈希表 下次直接调用返回
        public static int minStickers3(String[] stickers, String target) {
            //将贴纸数组转换成词频数组
            int N = stickers.length;
            int[][] counts = new int[N][26];
            for (int i = 0; i < N; i++) {                //遍历词频数组 填充字母
                char[] ch = stickers[i].toCharArray();   //取出每个贴纸字符串转换成字符数组
                for (char c : ch) {                      //字符数组一一插入对应的词频数组索引中
                    counts[i][c - 'a']++;
                }
            }
    
            //定义一个哈希表 保存 字符串 需要的最少贴纸张数 默认空字符串 0
            HashMap<String,Integer> map = new HashMap<>();
            map.put("",0);
    
            //调用递归函数 返回结果
            int ans = process3(counts,target,map);
            //最后返回 如果结果值是最大值表示没有符合的情况返回-1  否则就存在结果
            return ans == Integer.MAX_VALUE ? -1 : ans;
        }
    
        //递归函数 最佳优化 记忆化搜索 添加缓存表
        public static int process3(int[][] stickers,String target,HashMap<String,Integer>dp){
            //记忆化搜索 如果当前目标值存在哈希表 则直接返回其对应的贴纸次数
            if(dp.containsKey(target)) return dp.get(target);
    
            //不存在 则与方法二相同优化操作逻辑
            //将目标值转换成词频数组
            char[] t = target.toCharArray();
            int[] tcounts = new int[26];
            for(char ch:t){
                tcounts[ch - 'a']++;
            }
            int min = Integer.MAX_VALUE;                    //定义最小值返回结果
            for(int i = 0; i< stickers.length;i++){         //开始遍历贴纸词频数组
                int[] sticker = stickers[i];                //取出每一个贴纸字符数组进行判断
                if(sticker[t[0] - 'a'] > 0){                //如果这个贴纸字符 存在目标字符t[0]首字母的内容 就进行获取该贴纸  关键优化 剪枝操作 减少其他重复判断
                    StringBuilder str = new StringBuilder();        //定义字符串 保存目标值选择了贴纸之后 相减字母剩余的字符串 进行下一层递归
                    for(int j = 0; j <26;j++){              //遍历词频数组 进行将目标值减去该选择的贴纸数组
                        if(tcounts[j] > 0){                 //目标值 应该是26个字母中有值的才是需要进行相减的
                           int num = tcounts[j] - sticker[j];
                            for(int k = 0; k < num; k++){        //相减后 剩余的字母个数num个 那么剩余字母就要累计Num次
                                str.append((char)(j + 'a'));             //字母就是 索引位置j 加上'a'字符 转换char类型就是原字母
                            }
                        }
                    }
                    String rest = str.toString();               //当前剩余字符串转换成rest  传递至下一层递归
                    min = Math.min(min, process3(stickers,rest,dp));
                }
            }
            int ans = min + (min == Integer.MAX_VALUE?0:1);     //最后返回min还要再加上上层的贴纸数1  需求先判断是否min是最大值 是则表示没有有效的情况 直接加0 不是最大值则表示存在有效贴纸数 所以加上第一个取得贴纸数1
            dp.put(target,ans);                                 //最后也要将对应目标值得最小贴纸数 添加到缓存表
            return ans;  //最后返回结果值给主程序调用
        }
    }

### 四、两个字符串的最长公共子序列长度 ###

> 给定两个字符串str1和str2，  
> 返回这两个字符串的最长公共子序列长度  
>   
> 比如 ： str1 = “a12b3c456d”,str2= “1ef23ghi4j56k”  
> 最长公共子序列是“123456”，所以返回长度6

package class19;
    
    /**
     * 给定两个字符串str1和str2，
     * 返回这两个字符串的最长公共子序列长度
     * <p>
     * 比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
     * 最长公共子序列是“123456”，所以返回长度6
     * <p>
     * // 链接：https://leetcode.com/problems/longest-common-subsequence/
     */
    public class LongestCommonSubsequence {
        //方法一： 暴力递归
        public static int longestCommonSubsequence1(String s1, String s2) {
            //边界判断
            if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) return 0;
            //字符串转换成字符数组
            char[] ch1 = s1.toCharArray();
            char[] ch2 = s2.toCharArray();
            //调用递归 开始尝试 从字符串最右边开始
            return process1(ch1, ch2, ch1.length - 1, ch2.length - 1);
        }
    
        /**
         * 递归函数 ch1[0...i]和ch2[0...j] 两个数组区间范围的最长公共子序列
         */
        public static int process1(char[] ch1, char[] ch2, int i, int j) {
    
            // 1.当索引位置都来到了0时 如果相等就返回1 不等就返回0
            if (i == 0 && j == 0) { //base case
                return ch1[i] == ch2[j] ? 1 : 0;
            }else if(i == 0){   //2.索引位置i来到0 而j还没到0，说明ch1[i]就只剩一个字符，ch2[j]不止一个，所以两者如果相等返回1 不等，就接着递归，ch2[0...j-1]的范围
                if(ch1[i] == ch2[j]){ //base case
                    return 1;  //相等就说明有共同子序列 返回1给上层调用累加
                }else{
                    return process1(ch1,ch2,i,j-1); //不相等就接着将j位置往前移  i不变 因为i=0，最后一个，j来到j-1 让ch2[0..j-1]与之比较
                }
            }else if(j == 0){   //3.索引位置j来到0 而i还没到0，说明ch2[j]就只剩一个字符，ch1[i]不止一个，所以两者如果相等返回1 不等，就接着递归，ch1[0...i-1]的范围
                if(ch1[i] == ch2[j]){
                    return 1;
                }else{
                    return process1(ch1,ch2,i-1,j); //不相等 就将i-1前移 继续递归比较
                }
            }else{  //4. i j 都不为0  也就是两个数组字符剩下不止一个
                //分情况分析： 1  不以i结尾的ch1  可能以j结尾的ch2 那么就i往前移 j保持不变
                int p1 = process1(ch1,ch2,i-1,j);
                //2 不以j结尾 可能以i结尾
                int p2 = process1(ch1,ch2,i,j-1);
                //3 以i j 结尾 那么就需要确保ch1[i] ch2[j]相等，结果集+1当前相等的一个字符  并且返回前移-1的结果, 不相等那么就返回0
                int p3 = ch1[i] == ch2[j] ? (1+ process1(ch1,ch2,i-1,j-1)):0;
    
                //最后返回三种情况的最大值
                return Math.max(p1, Math.max(p2,p3));
            }
        }
    
        //方法二： 动态规划
        public static int longestCommonSubsequence2(String s1, String s2) {
            //边界判断
            if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) return 0;
            //字符串转换成字符数组
            char[] ch1 = s1.toCharArray();
            char[] ch2 = s2.toCharArray();
            //根据递归函数参数，是对应两数组的长度 范围是整个数组长度 所以定义一个二维数组
            int N = s1.length();
            int M = s2.length();
            int[][] dp = new int[N][M];   //s1表示行， s2表示列
            //根据递归函数的逻辑条件 索引在0，0 可以初始化得到值 相等表示是公共子序列 返回1 否则0
            dp[0][0] = ch1[0] == ch2[0]?1:0;
            //i=0 就是第0行的逻辑赋值,遍历第0行的每一列M列  dp[0][0]已经赋值，就不需要再遍历
            for(int i = 1; i < M; i++){
                //当 字符s1第一个字符 与s2其他字符比较 相等，那么就表示公共子序列返回1 否则 根据递归函数返回得到是依赖前一列的 也就是左边的值
                dp[0][i] = ch1[0] == ch2[i]? 1: dp[0][i-1];
            }
    
            //j=0 就是第0列的逻辑赋值,遍历第0列的每一行N行  dp[0][0]已经赋值，就不需要再遍历
            for(int i = 1; i < N; i++){
                //当 字符s2第一个字符 与s1其他字符比较 相等，那么就表示公共子序列返回1 否则 根据递归函数返回得到是依赖前一行的 也就是上边的值
                dp[i][0] = ch1[i] == ch2[0]? 1: dp[i-1][0];
            }
    
            //到这里就已经初始化完 第一行第一列的值了 ， 根据我们的情况分析， i,j 其他位置的值 是依赖 i-1,j  i,j-1 也就是左边和上边
            for(int i = 1; i < N; i++){
                for(int j = 1; j<M;j++){
                    //从第二行第二列开始去赋值填充数
                    //根据递归函数的情况
                    int p1 = dp[i-1][j];     //不以i结尾的ch1  可能以j结尾的ch2 那么就i往前移 j保持不变
                    int p2 = dp[i][j-1];     2 不以j结尾 可能以i结尾
                    int p3 = ch1[i] == ch2[j] ? ( 1 + dp[i-1][j-1]):0; // //3 以i j 结尾 那么就需要确保ch1[i] ch2[j]相等，结果集+1当前相等的一个字符  并且返回前移-1的结果, 不相等那么就返回0
                    dp[i][j] = Math.max(p1, Math.max(p2,p3));   最后返回三种情况的最大值给dp[i][j]
                }
            }
            //递归函数传参是 数组最后一个索引位置 而我们遍历填充dp数组也是从左上到右下 最后值就是最后一个索引位置
            return dp[N-1][M-1];
        }
    }