暴力递归就是尝试

  1. 把问题转化为规模缩小了的同类问题的子问题
  2. 有明确的不需要继续进行递归的条件（base case）
  3. 有当得到了子问题的结果之后的决策过程
  4. 不记录每一个子问题的解
  5. 一定要学会怎么去尝试，因为这是动态规划的基础

    汉诺塔问题

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

  1. public class Code01_Hanoi {
  3.     public static void hanoi(int n) {
  4.         if (n > 0) {
  5.             func(n, n, "left", "mid", "right");
  6.         }
  7.     }
  9.     public static void func(int rest, int down, String from, String help, String to) {
  10.         if (rest == 1) {
  11.             System.out.println("move " + down + " from " + from + " to " + to);
  12.         } else {
  13.             func(rest - 1, down - 1, from, to, help);
  14.             func(1, down, from, help, to);
  15.             func(rest - 1, down - 1, help, from, to);
  16.         }
  17.     }
  19.     public static void main(String[] args) {
  20.         int n = 3;
  21.         hanoi(n);
  22.     }
  23. }

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

image.png

  1. public class PrintAllSubsquences {
  3.     public static void printAllSubsquence(String str) {
  4.         char[] chs = str.toCharArray();
  5.         process(chs, 0);
  6.     }
  8.     // 当前来到i位置，要和不要，走两条路
  9.     // 之前的选择，所形成的结果，是str
  10.     public static void process(char[] chs, int i) {
  11.         if (i == chs.length) {
  12.             System.out.println(String.valueOf(chs));
  13.             return;
  14.         }
  15.         process(chs, i + 1);
  16.         char tmp = chs[i];
  17.         chs[i] = 0;
  18.         process(chs, i + 1);
  19.         chs[i] = tmp;
  20.     }
  22.     public static void function(String str) {
  23.         char[] chs = str.toCharArray();
  24.         process(chs, 0, new ArrayList<Character>());
  25.     }
  27.     // 当前来到i位置，要和不要，走两条路
  28.     // res之前的选择，所形成的列表
  29.     public static void process(char[] chs, int i, List<Character> res) {
  30.         if(i == chs.length) {
  31.             printList(res);
  32.         }
  33.         List<Character> resKeep = copyList(res);
  34.         resKeep.add(chs[i]);
  35.         process(chs, i+1, resKeep); // 要当前字符的路
  36.         List<Character> resNoInclude = copyList(res);
  37.         process(chs, i+1, resNoInclude); // 不要当前字符的路
  38.     }
  40.     public static void printList(List<Character> res) {
  41.         // ...;
  42.     }
  44.     public static List<Character> copyList(List<Character> list){
  45.         return null;
  46.     }
  49.     public static void main(String[] args) {
  50.         String test = "abc";
  51.         printAllSubsquence(test);
  52.     }
  53. }

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

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

  1. public class PrintAllPermutations {
  3.     public static ArrayList<String> Permutation(String str) {
  4.         ArrayList<String> res = new ArrayList<>();
  5.         if (str == null || str.length() == 0) {
  6.             return res;
  7.         }
  8.         char[] chs = str.toCharArray();
  9.         process(chs, 0, res);
  10.         res.sort(null);
  11.         return res;
  12.     }
  14.     public static void process(char[] chs, int i, ArrayList<String> res) {
  15.         if (i == chs.length) {
  16.             res.add(String.valueOf(chs));
  17.         }
  18.         boolean[] visit = new boolean[26]; // 注释掉
  19.         for (int j = i; j < chs.length; j++) {
  20.             // 这叫分支限界，提前杀死不可能走的路
  21.             if (!visit[chs[j] - 'a']) { // 注释掉 就是没有重复的排列
  22.                 visit[chs[j] - 'a'] = true; // 注释掉
  23.                 swap(chs, i, j);
  24.                 process(chs, i + 1, res);
  25.                 swap(chs, i, j);
  26.             }
  27.         }
  28.     }
  30.     public static void swap(char[] chs, int i, int j) {
  31.         char tmp = chs[i];
  32.         chs[i] = chs[j];
  33.         chs[j] = tmp;
  34.     }
  35. }

取牌游戏

image.png

  1. public class CardsInLine {
  3.     public static int win1(int[] arr) {
  4.         if (arr == null || arr.length == 0) {
  5.             return 0;
  6.         }
  7.         return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
  8.     }
  10.     public static int f(int[] arr, int i, int j) {
  11.         if (i == j) {
  12.             return arr[i];
  13.         }
  14.         return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
  15.     }
  17.     public static int s(int[] arr, int i, int j) {
  18.         if (i == j) {
  19.             return 0;
  20.         }
  21.         return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
  22.     }
  23.     // 动态规划
  24.     public static int win2(int[] arr) {
  25.         if (arr == null || arr.length == 0) {
  26.             return 0;
  27.         }
  28.         int[][] f = new int[arr.length][arr.length];
  29.         int[][] s = new int[arr.length][arr.length];
  30.         for (int j = 0; j < arr.length; j++) {
  31.             f[j][j] = arr[j];
  32.             for (int i = j - 1; i >= 0; i--) {
  33.                 f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
  34.                 s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
  35.             }
  36.         }
  37.         return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
  38.     }
  40.     public static void main(String[] args) {
  41.         int[] arr = { 1, 9, 1 };
  42.         System.out.println(win1(arr));
  43.         System.out.println(win2(arr));
  44.     }
  45. }

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

public class ReverseStackUsingRecursive {

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

    public static int getAndRemoveLastElement(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
        }
    }

    public static void main(String[] args) {
        Stack<Integer> test = new Stack<Integer>();
        test.push(1);
        test.push(2);
        test.push(3);
        test.push(4);
        test.push(5);
        reverse(test);
        while (!test.isEmpty()) {
            System.out.println(test.pop());
        }
    }
}

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

public class ConvertToLetterString {

    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    // i... 有多少种转化的结果
    public static int process(char[] chs, int i) {
        if (i == chs.length) {
            return 1;
        }
        if (chs[i] == '0') {
            return 0;
        }
        if (chs[i] == '1') {
            int res = process(chs, i + 1); // i自己作为单独的部分，后续有多少种方法
            if (i + 1 < chs.length) {
                res += process(chs, i + 2); //（i和i+1）作为单独的部分，后续有多少种方法
            }
            return res;
        }
        if (chs[i] == '2') {
            int res = process(chs, i + 1); // i自己作为单独的部分，后续有多少种方法
            //（i和i+1）作为单独的部分并且没有超过26，后续有多少种方法
            if (i + 1 < chs.length && (chs[i + 1] >= '0' && chs[i + 1] <= '6')) {
                res += process(chs, i + 2); //（i和i+1）作为单独的部分，后续有多少种方法
            }
            return res;
        }
        // str[i] == '3' ~ '9'
        return process(chs, i + 1);
    }

    public static void main(String[] args) {
        System.out.println(number("11111"));
    }
}

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

public class Knapsack {

    public static int maxValue1(int[] weights, int[] values, int bag) {
        return process1(weights, values, 0, 0, bag);
    }
    // i... 的货物自由选择，形成的最大价值返回
    // 重要永远不要超过bag
    // 之前做的决定，所达到的重量，alreadyweight
    public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
        if (alreadyweight > bag) {
            return 0;
        }
        if (i == weights.length) {
            return 0;
        }
        return Math.max(
            // 不要当前i号货物的价值
            process1(weights, values, i + 1, alreadyweight, bag),
            // 要当前i号货物的价值
            values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
    }

    public static int maxValue2(int[] c, int[] p, int bag) {
        int[][] dp = new int[c.length + 1][bag + 1];
        for (int i = c.length - 1; i >= 0; i--) {
            for (int j = bag; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (j + c[i] <= bag) {
                    dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7 };
        int[] values = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(maxValue1(weights, values, bag));
        System.out.println(maxValue2(weights, values, bag));
    }
}