递归 -> 记忆化搜索 (dp)-> 严格表结构（dp）

某些问题上 记忆化搜索和严格表结构时间复杂度相同

机器人走路问题

有N个格子，机器人初始在的位置S，目标位置是E，机器人可以向左或向右行走，每次走一步，可以走的步数为K步，问机器人有几种走法

暴力递归

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
// 暴力递归
public int walkWays(int N, int E, int S, int K) {
    return f1(N, E, K, S);
}

/**
     * 递归方法
     *
     * @param N    固定参数，一共有N个位置
     * @param E    固定参数，目标位置E
     * @param rest 还剩下几步要走
     * @param cur  当前所在位置
     * @return 方法有多少种走法
     */
public int f1(int N, int E, int rest, int cur) {
    // basecase 已经无法行走了, 看当前位置是不是目标位置
    if (rest == 0) {
        return cur == E ? 1 : 0;
    }

    // 已经在最左，不能向左走了
    if (cur == 1) {
        return f1(N, E, rest - 1, 2);
    }
    // 已经在最右不能，向右走了
    if (cur == N) {
        return f1(N, E, rest - 1, N - 1);
    }

    // 向左走，向右走
    return f1(N, E, rest - 1, cur - 1) + f1(N, E, rest, cur + 1);
}

只有可变参数是影响当前方法结果的，当可变参数rest和cur定了后结果就确定了，

分析递归

1
2
3
4
5
6
7
N=5,E=4,K=4,S=2

第一步
f(4,2) 走 f(3,1) f(3,3)
第二步
f(3,1) 走 f(2,2)
f(3,3) 走 f(2,2) f(2,4)

可以看到在计算时，f(2,2),这个结果被多次计算，如果将这个计算结果保存到一个表结构中，后序遇到时直接取出，就可以避免重复计算，利用空间换时间，这就记忆化搜索

记忆化搜索

记忆化搜索，使用一个表结构保存每次计算结果的值，这个表结构与可变参数的范围有关。

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
34
35
36
37
38
39
40
41
42
43
// 记忆化搜索
public int walkWays2(int N, int E, int S, int K) {
    // 表的大小和可变参数的大小有关
    int[][] dp = new int[K + 1][N + 1];
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= N; j++) {
            dp[i][j] = -1;
        }
    }
    return f2(N, E, K, S, dp);
}

/**
     * 递归方法
     *
     * @param N    固定参数，一共有N个位置
     * @param E    固定参数，目标位置E
     * @param rest 还剩下几步要走
     * @param cur  当前所在位置
     * @param dp   记忆表
     * @return 方法有多少种走法
     */
public int f2(int N, int E, int rest, int cur, int[][] dp) {
    if (dp[rest][cur] != -1) {
        return dp[rest][cur];
    }
    // basecase 已经无法行走了, 看当前位置是不是目标位置
    if (rest == 0) {
        dp[rest][cur] = cur == E ? 1 : 0
            return dp[rest][cur];
    }

    // 已经在最左，不能向左走了
    if (cur == 1) {
        dp[rest][cur] = f2(N, E, rest - 1, 2, dp);
    } else if (cur == N) { // 已经在最右不能，向右走了
        dp[rest][cur] = f2(N, E, rest - 1, N - 1, dp);
    } else {  // 向左走，向右走
        dp[rest][cur] = f2(N, E, rest - 1, cur - 1, dp) + f2(N, E, rest, cur + 1, dp);
    }

    return dp[rest][cur];
}

使用暴力递归的方式时间复杂度为O(2^k)是指数级别的，使用记忆化搜索是O(NK)

动态规划

从dp表开始看·

basecase为rest=0 那么可以看出第一排为0,0,0,1,0

  1. cur == 1 下面的每一排都依赖于上面 [rest-1]][cur + 1]位置的值，右上角的值
  2. cur == N 下面的每一排都依赖于上面 [rest-1]][cur - 1]位置的值，左上角的值
  3. 下面的每一排都依赖于上面 [rest-1]][cur + 1]+ [rest-1]][cur - 1]位置的值，左上角的值+右上角的值

下面的每一排都依赖于上面 [rest-1]

0 1 2 3 4 5
0 x 0 0 0 1 0
1 x 0 0 1 0 1
2 x 0 1 0 2 0
3 x 1 0 3 0 2
4 x 0 4 0 5 0

严格表结构的动态规划，动态规划是注意在于位置依赖的顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int walkWays3(int N, int E, int S, int K) {
    // 表的大小和可变参数的大小有关
    
    int[][] dp = new int[K + 1][N + 1];
    dp[0][S] = 1;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            if (j == 1){
                dp[i][j] = dp[i - 1][2];
            }else if (j == N){
                dp[i][j] = dp[i - 1][N - 1];
            }else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
        }
    }
    return dp[K][E];
}

由结果来看每一步的结果都只与上一步结果有关，由此可以进行空间压缩，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 动态规划
public int walkWays4(int N, int E, int S, int K) {
    int[] dp = new int[N + 1];
    dp[S] = 1;
    for (int i = 1; i <= K; i++) {
        int leftUp = dp[1]; // 左上角的值，需要临时变量来保存左上角的值
        for (int j = 1; j <= N; j++) {
            int tmp = dp[j];
            if (j == 1){
                dp[j] = dp[j + 1];
            }else if (j == N){
                dp[j] = leftUp;
            }else {
                dp[j] = leftUp +dp[j + 1];
            }
            leftUp = tmp;
        }
    }
    return dp[E];
}

记忆化搜索变为 严格意义上的动态规划

  1. 分析可变参数的变化范围
    • 单可变参数的维度，维度保证是一维
    • 可变参数的个数，参数个数尽量少
  2. 标出计算的终止位置
  3. 标出basecase
  4. 看要求的位置是如何依赖其他位置的
  5. 确定表计算的顺序，从哪些格子计算到哪些格子

马到底最终位置的方法数

有个棋盘（10x9），马的位置在（0,0），经过k步马最终的坐标(a，b)，问方法数一共是多少。

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
public int getWays(int x, int y, int k) {
    return process(x, y, k);
}

/**
 * 从（x,y）位置出发，去往(0,0)位置，必须跳step步的解法有多少种
 *
 * @param x    横坐标
 * @param y    纵坐标
 * @param step 步数
 * @return 方法有多少种
 */
public int process(int x, int y, int step) {
    if (x < 0 || x > 8 || y < 0 || y > 9) {
        return 0;
    }
    // basecase
    if (step == 0) {
        return (x == 0 && y == 0) ? 1 : 0;
    }
    // 马 的跳法
    return process(x - 1, y + 2, step - 1)
            + process(x + 1, y + 2, step - 1)
            + process(x + 2, y + 1, step - 1)
            + process(x - 2, y + 1, step - 1)
            + process(x - 1, y - 2, step - 1)
            + process(x + 1, y - 2, step - 1)
            + process(x - 2, y - 1, step - 1)
            + process(x + 2, y - 1, step - 1);
}

可变参数有3个，准备3维的dp表,类似于立方体。

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 int dpWays(int x, int y, int step) {
    if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) {
        return 0;
    }
    int[][][] dp = new int[9][10][step + 1];
    // 只有这个位置是1
    dp[0][0][0] = 1;
    for (int h = 1; h <= step; h++) { // 从第1层开始
        // 穷举x,y
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 10; c++) {
                dp[r][c][h] += getValue(dp, r - 1, c + 2, h - 1);
                dp[r][c][h] += getValue(dp, r - 1, c - 2, h - 1);
                dp[r][c][h] += getValue(dp, r + 1, c + 2, h - 1);
                dp[r][c][h] += getValue(dp, r + 1, c - 2, h - 1);
                dp[r][c][h] += getValue(dp, r - 2, c + 1, h - 1);
                dp[r][c][h] += getValue(dp, r - 2, c - 1, h - 1);
                dp[r][c][h] += getValue(dp, r + 2, c + 1, h - 1);
                dp[r][c][h] += getValue(dp, r + 2, c - 1, h - 1);
            }
        }

    }
    return dp[x][y][step];
}

// 防止越界
public int getValue(int[][][] dp, int row, int col, int step) {
    if (row < 0 || row > 8 || col < 0 || col > 9) {
        return 0;
    }
    return dp[row][col][step];
}

凑硬币问题

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

从第一种硬币开始试，第一种1张、2张… 不能超过最大金额

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// arr里都是正数，没有重复值，每一个值代表一 种货币，每一种都可以用无限张
// 最终要找零钱数是aim,
// 找零方法数返回
public int way1(int[] arr, int aim) {
    return process(arr, 0, aim);
}

// 可以自由使用arr[index...]所有的面值
// 需要搞定的钱数是rest
// 返回找零的方法数
public int process(int[] arr, int index, int rest) {
    if (index == arr.length) {
        return rest == 0 ? 1 : 0;
    }
    // arr[index] 0张 1张... 不要超过rest的钱数
    int ways = 0;
    for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
        ways += process(arr, index + 1, rest - arr[index] * zhang);
    }
    return ways;
}

转换为动态规划

查看basecase， rest == 0的位置是1其余位置为0

看其余位置的依赖关系，假设硬币为1,2,3

1
2
3
4
5
	0 	1	2	3
0
1				?
2		需要		需要
3 	1	0	0	0

对于?位置，当数量为0时ways+=rest，张数等于1的时候需要rest - arr[index] * zhang列的位置。是一个累加的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int dp(int[] arr, int aim) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    for (int index = N - 1; index >= 0; index--) { // 从下往上
        for (int rest = 0; rest <= aim; rest++) {
            int ways = 0;
            for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
                ways += dp[ index + 1][ rest - arr[index] * zhang];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}

对于中间的枚举每张钞票行为，真的有必要吗？从数学上看

1
2
... x y
a b c d

对于y来说需要 a+b+c+d, 对于x来说需要a+b+c ,对于每一行，你前的某个值已经计算过这些了,所有对于y来说只需要x+d就可以了。所以结果为：dp[index][rest] = dp[index + 1][rest];同时如果结果不出界的话rest - arr[index] >= 0是dp[index][rest] += dp[index][rest - arr[index]];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int dp2(int[] arr, int aim) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    dp[N][0] = 1;
    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]]; // 之前的值已经被rest - arr[index]计算过了
            }
        }
    }
    return dp[0][aim];
}