0%

递归和动态规划

发表于 更新于 分类于

递归和动态规划问题

  • 介绍:
    • 暴力递归:
      1. 把问题转化为规模缩小了的同类问题的子问题
      2. 有明确的不需要继续进行递归的条件(base case)
      3. 有当得到了子问题的结果之后的决策过程
      4. 不记录每一个子问题的解
    • 动态规划:
      1. 从暴力递归中来
      2. 将每一个子问题的解记录下来, 避免重复计算
      3. 把暴力递归的过程, 抽象成了状态表达
      4. 并且存在简化状态表达, 使其更加简洁的可能

递归

  1. 阶乘
    1
    2
    3
    4
    5
    6
    public static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
  2. 汉诺塔
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public static void hanoi(int N, String from, String help, String to) {
        String format = String.format("Number: %d, From %s Use %s To %s", N, from, help, to);
        if (N == 1) {
            System.out.println(format);
        } else {
            hanoi(N - 1, from, to, help);
            System.out.println(format);
            hanoi(N - 1, help, from, to);
        }
    }
  3. 打印一个字符串的所有子序列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public static void printSubStr(String str) {
        printSubStrProcess(str.toCharArray(), 0, "");
    }

    public static void printSubStrProcess(char[] str, int i, String res) {
        if (i == str.length) {
            System.out.println(res);
        } else {
            printSubStrProcess(str, i + 1, res);
            printSubStrProcess(str, i + 1, res + str[i]);
        }
    }
  4. 打印一个字符串的全排列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public static void printPermutation(String str) {
        printPermutationProcess(str, "", str.length());
    }

    public static void printPermutationProcess(String str, StringBuffer res, int length) {
        if (res.length() == length) {
            System.out.println(res.toString());
        } else {
            for (int i = 0; i < str.length(); i++) {
                res.append(str.charAt(i));
                printPermutationProcess(str.substring(0, i) + str.substring(i + 1), res, length);
                res.deleteCharAt(res.length() - 1);
            }
        }
    }
  5. 母牛每年生一只母牛, 新出生的母牛成长三年后也能每年生一只, 求N年后母牛的数量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public static int getCows(int N) {
        if (N < 5) {
            return N;
        } else {
            return getCows(N - 1) + getCows(N - 3);
        }
        // return getCowsProcess(N, 0, 0, 1, 1);
    }

    public static int getCowsProcess(int N, int c1, int c2, int c3, int current) {
        if (current == N) {
            return c1 + c2 + c3;
        } else {
            return getCowsProcess(N, c3, c1, c2 + c3, current + 1);
        }
    }

动态规划

  1. 给定一个二维数组, 二维数组中的每个数都是正数, 要求从左上角走到右下角, 每一步只能向右或者向下. 沿途经过的数字要累加起来. 返回最小的路径和.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int getMinPathSum(int[][] arr) {
    if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0) {
        return 0;
    }
    int[][] sum = new int[arr.length][arr[0].length];
    sum[sum.length - 1][sum[sum.length - 1].length - 1] = arr[arr.length - 1][arr[arr.length - 1].length - 1];
    for (int i = arr.length - 2; i >= 0 ; i--) {
        sum[i][sum[i].length - 1] = sum[i][sum[i].length - 1] + arr[i][arr[i].length - 1];
    }
    for (int i = arr[0].length - 2; i >= 0 ; i--) {
        sum[sum.length - 1][i] = sum[sum.length - 1][i + 1] + arr[arr.length - 1][i];
    }
    for (int i = arr.length - 2; i >= 0; i--) {
        for (int j = arr[i].length - 2; j >= 0; j--) {
            sum[i][j] = arr[i][j] + Math.min(sum[i + 1][j], sum[i][j + 1]);
        }
    }
    return sum[0][0];
}
  1. 给定一个数组arr, 和一个整数aim. 如果可以任意选择arr中的数字(每个数字只能使用一次), 能不能累加得到aim? 若能返回true, 否则返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static boolean isSum(int[] arr, int aim) {
    int max = 0, min = 0;
    for (int item : arr) {
        if (item > 0) {
            max += item;
        }
        if (item < 0) {
            min += item;
        }
    }
    Map<Integer, Boolean>[] res = new Map[arr.length + 1];
    for (int i = 0; i < res.length; i++) {
        res[i] = new HashMap<>();
    }
    res[res.length - 1].put(aim, true);
    for (int i = arr.length - 1; i >= 0; i--) {
        Map<Integer, Boolean> last = res[i + 1];
        Map<Integer, Boolean> current = res[i];
        for (int j = min; j <= max; j++) {
            boolean tmp1 = last.get(j) == null ? false : last.get(j);
            boolean tmp2 = last.get(j + arr[i]) == null ? false : last.get(j + arr[i]);
            current.put(j, tmp1 || tmp2);
        }
    }
    return res[0].get(0) == null ? false : res[0].get(0);
}

public static boolean notizer(int[] arr, int aim, int sum, int index) {
    if (index == arr.length) {
        return aim == sum;
    }
    return notizer(arr, aim, sum, index + 1) || notizer(arr, aim, sum + arr[index], index + 1);
}