暴力递归：动态规划的雏形

Bertha 。 2024-03-25 18:26 15阅读 0赞

一.暴力递归的基本概念：

1.  什么是暴力递归？简而言之，**暴力递归就是尝试，与此同时，暴力递归是动态规划的前身，换句话说：动态规划是对暴力递归的优化。**

1.  关于解决暴力递归的基本步骤：

1.  把问题转化为规模缩小了的同类问题的子问题

1.  有明确的不需要继续进行递归的条件（base case)

1.  有当得到了子问题的结果之后的决策过程

1.  不记录每一个子问题的解

二.结合实例去切实理解暴力递归的过程：

**2.1打印一个字符串的全部子序列（子集），包括空字符串**

> 题目描述：  
> 给定字符串 ，列出这个字符串的所有子序列情况：需要注意子序列和子字符串的区别： 子串是字符串中的由连续字符组成的一个序列，重点在于连续。例如，"1AB2345CD"，那么"1AB23"，"5CD"都是相应的子串，而"12345CD"不是，已经不是连续的状态， 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串，那么很明显，子序列和子串最大的区别就是可以是不连续的。例如，"1AB2345CD"，"12345CD"就是它的一个子序列。  
>

我们描述一下我们解决问题的思路：按照我们上面总结的暴力递归的思路，我们对这个问题进行个性化的思路求解：对于字符串的每一个字符而言，都有**加入字符串和不加入字符串两种选择**，如果将字符加入字符串，**下一个递归的字符串将被修改（加上当前字符）**，否则原来字符串**保持原样进入下一次递归，直到递归到最后一个元素，递归结束。**

代码如下：

public class Subsequence {
        public static void main(String[] args) {
            String s="abcde";
            System.out.println(allSubsequence(s));
        }
        public static List<String> allSubsequence(String target){
            //将字符串转化为字符数组（便于遍历）
            char[]chars=target.toCharArray();
            //创建结果集
            LinkedList<String> end = new LinkedList<>();
            int index=0;//定义遍历位置
            process(chars,end,index,"");
            return end;
        }
    
        private static void process(char[] chars, LinkedList<String> end, int index,String path) {
            //确认终止条件
            if(index==chars.length){
                //将结果加入到结果集
                end.add(path);
                return ;
            }
            //对于当前结点有两种处理策略：1.当前结点不加入结果集2.当前结点加入结果集
            //当前结果不加入结果集
            String no=path;
            //进入下一层递归
            process(chars, end, index+1, no);
            //当前结果加入结果集
            String yes=path+String.valueOf(chars[index]);
            //进入下一层递归
            process(chars, end, index+1, yes);
        }
    }

我们在此基础上再思考一个问题：如果要求字符串中的每个字符不重复呢？

答案相对简单，将用来收集结果的容器由队列调整为hashmap即可，代码如下：

public class SubsequenceForNoRepeat {
        public static void main(String[] args) {
            String s="aaaaa";
            System.out.println(allSubsequence(s));
        }
    
        public static List<String> allSubsequence(String target){
            //将字符串转化为字符数组（便于遍历）
            char[]chars=target.toCharArray();
            //创建结果集
            HashSet<String> end = new HashSet<>();
            LinkedList<String> list = new LinkedList<>();
            int index=0;//定义遍历位置
            process(chars,end,index,"");
            //将hashset遍历进list
            for (String individual:end) {
                list.add(individual);
            }
            return list;
        }
    
        private static void process(char[] chars, HashSet<String> end, int index, String path) {
            //确认终止条件
            if(index==chars.length){
                //将结果加入到结果集
                end.add(path);
                return ;
            }
            //对于当前结点有两种处理策略：1.当前结点不加入结果集2.当前结点加入结果集
            String no=path;
            process(chars, end, index+1, no);
            String yes=path+String.valueOf(chars[index]);
            process(chars, end, index+1, yes);
        }
    }

**2.2打印一个字符串的全部排列**

> 问题描述：输入一个无重复字符的字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解题思路：将字符串转化为字符数组，对于一个位置的字符而言，能**和它后面的元素进行交换（利用循环），交换之后进行递归**，进入下一个数组元素的排列，递归的出口是当字符数组的最后一个元素排列结束，同时需要注意的是：由于我们排列过程中是对原数据（原本的字符数组）进行操作，这也就意味着当我们跳**出一层递归再回到上一层的元素时，我们要将原来的数据进行恢复**

![8aaed336810f1520e73380f5551e0212.png][]

代码如下：

package violencerecursion;
    
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * @author tongchen
     * @create 2023-03-15 17:17
     */
    public class FullArrangement {
        public static void main(String[] args) {
            String s="abc";
            System.out.println(arrange(s));
        }
        public static List<String> arrange(String s){
            //将字符串转化为字符数组
            char []chars=s.toCharArray();
            //创建结果集
            LinkedList<String> list = new LinkedList<>();
            //递归处理
            process(chars,0,list);
            return list;
        }
    
        private static void process(char[] chars, int i, LinkedList<String> strings) {
            //递归的出口
            if(i== chars.length){
                strings.add(String.valueOf(chars));
                return ;
            }
            //循环递归（思路：从当前结点开始往下的下标都能进行全排列，之前的结点都已经排列好了）
            for(int j=i;j< chars.length;++j){
                //交换其中两个
                swap(chars,i,j);
                //从此往下继续递归
                process(chars, i+1, strings);
                //恢复
                swap(chars, i,j );
            }
        }
    
        private static void swap(char[] chars, int i, int j) {
            char temp=chars[i];
            chars[i]=chars[j];
            chars[j]=temp;
        }
    }

同理，我们对这个问题加入进一步的条件限制：最后的输出结果中不允许存在重复元素：在这里存在两种解题思路：①利用hashmap等到最后数据加入结果集时判断当前结果集是否包含这个元素，代码如下：

package violencerecursion;
    
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * @author tongchen
     * @create 2023-03-15 23:01
     */
    public class FullArrangementNoRepeat {
        //思路：第一种思路很简单，把存放结果的容器由list转化为set,解决重复问题，但这种效率相对较低
        public static void main(String[] args) {
            String s="aaa";
            System.out.println(arrange(s));
        }
        public static List<String> arrange(String s){
            //将字符串转化为字符数组
            char []chars=s.toCharArray();
            //创建map
            HashSet<String> set = new HashSet<>();
            //创建结果集
            LinkedList<String> list = new LinkedList<>();
            //递归处理
            process(chars,0,set);
            //最后将结果复制到list
            for (String s1: set) {
                list.add(s1);
            }
            return list;
        }
    
        private static void process(char[] chars, int i, HashSet<String> strings) {
            //递归的出口
            if(i== chars.length){
                strings.add(String.valueOf(chars));
                return ;
            }
            //循环递归（思路：从当前结点开始往下的下标都能进行全排列，之前的结点都已经排列好了）
            for(int j=i;j< chars.length;++j){
                //交换其中两个
                swap(chars,i,j);
                //从此往下继续递归
                process(chars, i+1, strings);
                //恢复
                swap(chars, i,j );
            }
        }
    
        private static void swap(char[] chars, int i, int j) {
            char temp=chars[i];
            chars[i]=chars[j];
            chars[j]=temp;
        }
    }

②**利用分支限界，在每一个元素加入时都要判断在结果中是否存在这种情况，一旦存在，直接放弃此次递归，加入下次循环**

package violencerecursion;
    
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * @author tongchen
     * @create 2023-03-15 23:12
     */
    public class FullArrangementBranchGauge {
        public static void main(String[] args) {
            String s="aaa";
            System.out.println(fullArrangement(s));
        }
        public static List<String> fullArrangement(String s){
            //创建新list
            LinkedList<String> list = new LinkedList<>();
            //将数组转化为字符串
            char[] chars = s.toCharArray();
            //从开头的位置不断向后递归
            process(chars,0,list);
            return list;
        }
    
        private static void process(char[] chars, int i, LinkedList<String> list) {
            //设置终止条件
            if(i== chars.length){
                //将排列的结果加入字符数组
                list.add(String.valueOf(chars));
            }
            //创建一个负责检查当前位置是否重复的哈希表，如果当前位置重复，直接不走当前路径
            boolean [] checks=new boolean[26];
            //从当前位置开始与往后的字符交换生成结果
            for (int j = i; j <chars.length ; j++) {
                if(!checks[chars[j]-'a']){
                    checks[chars[j]-'a']=true;
                    swap(chars, i,j );
                    //进入下一个位置
                    process(chars, i+1, list);
                    //恢复
                    swap(chars,j,i);
                }
                //直接跳过
            }
        }
        private static void swap(char[] chars, int i, int j) {
            char temp=chars[i];
            chars[i]=chars[j];
            chars[j]=temp;
        }
    }

我们来分析这两种不同的解决问题的思路：一种是到最后的结果再进行去重，一种是对于每一个元素都要进行检查，一旦发现重复就排除这种情况，相比之下，显然是后者的效率更高。

**2.3给定一个整型数组arr，代表数值不同的纸牌排成一条线。**

力扣连接：[https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/][https_leetcode.cn_problems_ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof]

解题思路：对于数字是1，我们分为两种情况：①当前数字直接转化为字母②与后面的数字共同转化为字母；对于数字是2的情况，同样分为两种情况：①当前数字直接转化为字母②如果后面数字是0-5，与后面的数字共同转化为字母；如果数字是3,只能自己转化为字母，只有一种情况，如果是0,只能和后面的元素组成一个字母，也只有一种情况。递归出口是当超过最后一个元素，解决完当前数字向下一个数字进行递归

代码如下：

package violencerecursion;
    
    /**
     * @author tongchen
     * @create 2023-03-15 23:40
     */
    public class NumConvert {
        public static void main(String[] args) {
            String s="12345";
            System.out.println(convert(s));
    
        }
        //创建转化函数
        public static int convert(String s){
            //将字符串转化为字符数组
            char[] chars = s.toCharArray();
            //进行递归
          return  process(chars,0);
        }
    
        private static int process(char[] chars, int i) {
            //检查递归的出口
            if(i== chars.length){
                return 1;
            }
            //如果是1和2，可能存在两种情况
            if(chars[i]=='1'){
                int res=process(chars, i+1);
                //判断第二种情况，结果直接在1的基础上进行相加即可
                if((i+1)< chars.length){
                    res+=process(chars, i+2);
                }
                return res;
            }
            //如果是2，也要进行分类讨论
           else if(chars[i]=='2'){
                int res=process(chars, i+1);
                if((i+1)< chars.length&&chars[i+1]<='5'){
                    res+=process(chars, i+2);
                }
                //注意要将结果直接返回，不继续向下遍历了
                return res;
            }
            //如果是3-9，就只有一种情况了
            else{
                return process(chars, i+1);
            }
        }
    }

**2.4背包问题：**

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

解题思路:对于背包问题，我们的解决思路如下：对于每一个序号的物品，都标有一定的重量，我们对现有背包已经有的元素进行标记，当当前背包的重量大于背包的最大容量或者当我们抵达最后一个元素的时候，递归结束，同样对于存在的每一个物品，都有放入背包和不放入背包两种选择，每次递归回溯之前都会返回当前不同选择方案下往背包中存放容量的最大值。

package violencerecursion;
    
    /**
     * @author tongchen
     * @create 2023-03-16 23:52
     */
    public class Bag {
        public static void main(String[] args) {
            int[]w={3,4,5};
            int[]v={6,4,8};
            System.out.println(bestBag(w, v, 10));
        }
        public static int bestBag(int []w,int []v,int weight){
            //检查有效性
            if(w.length==1&&w[0]>weight){
                return 0;
            }
           return process(w,v,0,0,weight);
        }
        //递归过程
        private static int process(int[] w, int[] v, int index, int alWeight, int weight) {
            //判断出口
            if(alWeight>weight){
                return -1;
            }
            if(index==w.length){
                return 0;//成功
            }
            //第一种情况：当前节点上不放值
            int value1=process(w, v, index+1, alWeight, weight);
            //第二种情况：当前结点放入值
            int value2Next=process(w, v, index+1, alWeight+w[index], weight);
            int value2=-1;
            if(value2Next!=-1){
                value2=value2Next+v[index];
            }
            //返回两种结果的最大值
            return Math.max(value1, value2);
        }
    }

[8aaed336810f1520e73380f5551e0212.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1f3803da64504077a3429f0fe166adf6.png
[https_leetcode.cn_problems_ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof]: https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/