左程云 Java 笔记--暴力递归--动态规划

暴力递归–动态规划

暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程，
4，不记录每一个子问题的解

汉诺塔问题

打印n层汉诺塔从最左边移动到最右边的全部过程

public class hanoi {
    public static void main(String[] args) {
        int n =3;
        hanoi(n);
    }
    
    public static void hanoi(int n){
        if (n > 0){
            func(n,"左","中","右");
        }
    }

    public static void func(int i, String start, String end, String other){
        if (i == 1){
            System.out.println("move 1 from" + start + "to" + end);
        }else {
            func(i-1,start,other,end);
            System.out.println("move " + i + " from" + start + "to" + end);
            func(i-1,other,end,start);
        }
    }
}

例二–打印一个字符串的全部子序列

打印一个字符串的全部子序列，包括空字符串

public class PrintAllSubsquences {
    public static void main(String[] args) {
        String str = "abc";
        fun(str);
        PrintAllSubsquences(str);
    }

    public static void PrintAllSubsquences(String str){
        char[] chs = str.toCharArray();
        process(chs,0);
    }

    private static void process(char[] chs, int i) {
        if (i == chs.length){
            System.out.println(String.valueOf(chs));
            return;
        }
        process(chs,i+1);//要当前字符
        char temp = chs[i];
        chs[i] = 0;
        process(chs,i+1);
        chs[i] = temp;
    }
    
    private static void fun(String str){
        char[] chs = str.toCharArray();
        process(chs,0,new ArrayList<Character>());
    }
    
    //来到i 要不要两种选择
    //res 之前的选择形成的列表
    private static void process(char[] chs, int i, List<Character> res) {
        if (i == chs.length){
            printList(res);
            return;
        }
        List<Character> resKeep = copyList(res);
        resKeep.add(chs[i]);
        process(chs,i+1,resKeep);//要当前字符
        List<Character> resNoInclude = copyList(res);
        process(chs,i+1,resNoInclude);
    }

    private static List<Character> copyList(List<Character> res) {
        List<Character> l = new LinkedList<>();
        for (Character re : res) {
            l.add(re);
        }
        return l;
    }

    private static void printList(List<Character> res) {
        System.out.println(res);
    }
}

例三–打印一个字符串的全部排列

打印一个字符串的全部排列
打印一个字符串的全部排列，要求不要出现重复的排列（排列组合）

public class code3 {
    public static void main(String[] args) {

    }
    public static ArrayList<String> permutation(String str){
        ArrayList<String> res = new ArrayList<>();
        if (str == null || str.length() == 0) return res;
        char[] chs = str.toCharArray();
        process(chs,0,res);
        //res.sort(null);
        return res;
    }
    public static void process(char[] str, int i, ArrayList<String> res){
        if (i == str.length) res.add(String.valueOf(str));
        boolean[] visit = new boolean[26];
        for (int j = i; j < str.length; j++) {
            if (!visit[str[j]-'a']){
                visit[str[j]='a'] = true;
                swap(str,i,j);
                process(str,i+1,res);
                swap(str,i,j);
            }
        }
    }
    public static void swap(char[] str, int i, int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

例四

给定一个整型数组arr，代表数值不同的纸牌排成一条线。 玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
[举例]
arr=[1, 2, 100, 4]。
开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为[2, 100, 4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A. …如果开始时玩家A拿走4，则排列变为[1, 2, 100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A. …玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1，让排列变为[2, 100, 4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜,分数为101。所以返回101。
arr=[1, 100, 2]。
开始时，玩家A不管拿1还是2，玩家B作为绝项聪明的人，都会把100拿走。玩家B会获胜,分数为100。所以返回100。

暴力递归

   public static int wim(int[] arr){
        if (arr == null || arr.length == 0) return 0;
        return Math.max(f(arr,0, arr.length-1),s(arr,0, arr.length)-1);
    }

    public static int f(int[] arr,int i, int j){
        if (i == j) return arr[i];
        return Math.max(arr[i] + s(arr,i+1,j),
                arr[j]+s(arr,i,j-1));
    }

    private static int s(int[] arr, int i, int j) {
        if (i == j) return 0;
        return Math.min(f(arr,i+1,j),f(arr,i,j-1));
    }

动态规划

   public static int win2(int[] arr){
        if (arr == null || arr.length == 0) return 0;
        int N = arr.length;
        int[][] f = new int[N][N];
        int[][] s = new int[N][N];
        for (int i = 0; i < N; i++) {
            f[i][i] = arr[i];
        }
        for (int i = 1; i < N; i++) {
            int L = 0;
            int R = i;
            while (L < N && R < N){

                f[L][R] = Math.max(arr[L] + s[L+1][R], arr[R]+s[L][R-1]);
                s[L][R] = Math.min(f[L+1][R],f[L][R-1]);

                L++;
                R++;
            }
        }

        return Math.max(f[0][N-1],s[0][N-1]);
        
    }

逆序栈

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。
如何实现?

   public static void reverse(Stack<Integer> s){
        if (s.isEmpty()) return;
        int i = f(s);
        reverse(s);
        s.push(i);
    }

    public static int f(Stack<Integer> s){
        int res = s.pop();
        if (s.isEmpty()){
            return res;
        }else {
            int last = f(s);
            s.push(res);
            return last;
        }
    }

例六

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

暴力递归

public class code6 {
    public static void main(String[] args) {
        
    }

    public static int process(char[] str, int i){
        if (i == str.length) return 1;
        if (str[i] == '0') return 0;
        if (str[i] == '1'){
            int res = process(str,i+1); //单独一部分
            if (i+1 < str.length){
                res += process(str,i+2);//i和i+1作为一部分
            }
            return res;
        }
        if (str[i] == '2'){
            int res = process(str,i+1);
            if (i+1 < str.length && (str[i+1] >= '0' && str[i+1] <= '6')){
                res += process(str,i+2);
            }
            return res;
        }
        //'3' -- '9'
        return process(str,i+1);
    }
}

动态规划

   public static int dpways2(String s){
        if (s == null || s.length() == 0) return 0;
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N+1];
        dp[N] = 1;
        //从右往左走
        for (int i = N-1; i >= 0; i--) {
            if (str[i] == '0') dp[i] = 0;
            if (str[i] == '1'){
                dp[i] = dp[i+1]; //单独一部分
                if (i+1 < N){
                    dp[i] += dp[i+2];//i和i+1作为一部分
                }
            }
            if (str[i] == '2'){
                dp[i] = dp[i+1];
                if (i+1 < str.length && (str[i+1] >= '0' && str[i+1] <= '6')){
                    dp[i] += dp[i+2];
                }
            }
        }
        return dp[0];
    }

例七

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

暴力递归

public static int process(int[] weights, int[] values, int i, int alreadweight, int bag){
        if (alreadweight > bag) return 0;
        if (i == weights.length) return 0;
        return Math.max(
                process(weights,values,i+1,alreadweight,bag),

                values[i]+process(weights,values,i+1,
                        alreadweight+weights[i],bag)
        );
    }
public static int process2(int[] weights, int[] values, int i, int alreadweight, int alreadvalue, int bag){
        if (alreadweight > bag) return 0;
        if (i == weights.length) return alreadvalue;
        return Math.max(
                process2(weights,values,i+1,alreadweight,alreadvalue,bag),

                process2(weights,values,i+1,
                        alreadweight+weights[i],alreadvalue+values[i],bag)
        );
    }

动态规划

   public static int dpway(int[] w, int[] v, int bag){
        int N = w.length;
        int[][] dp = new int[N+1][bag+1];
        for (int index = N-1; index >= 0; index--){
            for (int rest = 1; rest <= bag ; rest++) {
                int p1 = dp[index+1][rest];//不要这个物品
                int p2 = -1;
                if (rest - w[index] >= 0){
                    p2 = v[index] + dp[index+1][rest-w[index]];//要这个物品
                }
                dp[index][rest] = Math.max(p1,p2);
//                dp[index][rest] = dp[index+1][rest];
//                if (rest >= w[index]){
//                    dp[index][rest] = Math.max(dp[index][rest]
//                            ,dp[index+1][rest-w[index]]);
//                }
            }
        }
        return dp[0][bag];
    }

例八

假设有排成一行的N个位置，记为1~N，, N定大于或等于2
开始时机器人在其中的M位置上(M一定是1~N中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置;
如果机器人来到N位置，那么下一步只能往左来到N-1位置;
如果机器人来到中间位置，那么下一步可以往左走或者往右走;
规定机器人必须走K步，最终能来到P位置(P也是1 ~N中的一个)的方法有多少种
给定四个参数N、M、K、P，返回方法数。

递归

public static int ways1(int N, int M, int K, int P){
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N ) return  0;
        return walk1(N,M,K,P);
    }
    /**
     *
     * @param N 位置1-n
     * @param cur 当前位置
     * @param rest 剩余多少步可以走
     * @param P 目标位置
     * @return 方法有多少种
     */
    public static int walk1(int N, int cur, int rest,int P){
        if(rest == 0) return cur == P ? 1 : 0;
        if (cur == 1) return walk1(N,2,rest-1,P);
        if (cur == N) return  walk1(N,N-1,rest-1, P);
        return walk1(N,cur+1,rest-1,P)
                + walk1(N,cur-1,rest-1,P);
    }

缓存重复的数据–动态规划

public static int ways2(int N, int M, int K, int P){
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N ) return  0;
        int[][] dp = new int[N+1][K+1];//缓存所有的返回值
        //赋值为-1
        for (int row = 0; row <= N; row++) {
            for (int col = 0; col <= K; col++) {
                dp[row][col] = -1;
            }
        }
        return walk2(N,M,K,P,dp);
    }

    public static int walk2(int N, int cur, int rest,int P, int[][] dp){
        if (dp[cur][rest] != -1){
            return dp[cur][rest];
        }
        if(rest == 0){
            dp[cur][rest] = cur == P ? 1 : 0;
            return dp[cur][rest];
        }
        if (cur == 1){
            dp[cur][rest] = walk2(N,2,rest-1,P,dp);
            return dp[cur][rest];
        }
        if (cur == N){
            dp[cur][rest] = walk2(N,N-1,rest-1, P,dp);
            return dp[cur][rest];
        }
        dp[cur][ rest] = walk2(N,cur+1,rest-1,P,dp)
                + walk2(N,cur-1,rest-1,P,dp);
        return dp[cur][rest];
    }

如何改 动态规划

根据依赖计算格子中的数，然后找到 （M,K）返回

不是所有暴力递归都能转成动态规划
但是动态规划都来自暴力递归

常见的4种尝试模型
1)从左往右的尝试模型.
2)范围.上的尝试模型
3)多样本位置全对应的尝试模型
4)寻找业务限制的尝试模型

动态规划

例九

给定数组arr, arr中 所有的值都为正数且不重复
每个值代表一种面值的货币，每种面值的货币可以使用任意张
再给定一个整数aim，代表要找的钱数
求组成aim的方法数

暴力递归

public static int ways(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        return process(arr,0,aim);
    }

    //可以自由使用arr[index... ]所有的面值，每一种面值都可以使用任意张，
    //组成rest， 有多少种方法
    private static int process(int[] arr, int index, int rest) {
       // 可省
        // if (rest < 0) return 0;
        //rest >= 0
        if (index == arr.length){//没有可以选择得了
            return rest == 0 ? 1 : 0;
        }
        //当前有货币，arr[index]
        int ways = 0;
        for (int zhang = 0; zhang*arr[index] <= rest ; zhang++) {
            ways += process(arr,index +1,rest-zhang*arr[index]);
        }
        return ways;
    }

记忆化搜索

   public static int waysdp(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        //HashMap<String,Integer> map = new HashMap<>();  与下面等价
        int[][] dp = new int[arr.length+1][aim+1];
        //初始化为-1
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return processdp(arr,0,aim,dp);
    }
    //如果index和rest的组合没算过就是-1，如果算过必大于-1
    private static int processdp(int[] arr, int index, int rest, int[][] dp) {
        if (dp[index][rest] != -1) return dp[index][rest];
        // 可省
        // if (rest < 0) return 0;
        //rest >= 0
        if (index == arr.length){//没有可以选择得了
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        //当前有货币，arr[index]
        int ways = 0;
        for (int zhang = 0; zhang*arr[index] <= rest ; zhang++) {
            ways += processdp(arr,index +1,rest-zhang*arr[index],dp);
        }
        dp[index][rest] = ways;
        return dp[index][rest];
    }

动态规划

public static int way3(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1; // dp[N][1--aim] = 0
        for (int index = N-1; index >= 0 ; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; zhang*arr[index] <= rest ; zhang++) {
                    ways += dp[index +1][rest-zhang*arr[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

优化枚举的动态规划

？ = a+b+c+…
= 星 + a；
文章来源地址https://www.toymoban.com/news/detail-400325.html

    public static int way4(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1; // dp[N][1--aim] = 0
        for (int index = N-1; index >= 0 ; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index+1][rest];
                if (rest - arr[index] >= 0){
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

总结

到了这里，关于左程云 Java 笔记--暴力递归--动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！