算法12.从暴力递归到动态规划5

算法|12.从暴力递归到动态规划5

1.机器人行进问题

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

解题思路：

• 本题有对应的业务场景，但是我感觉解题其实是从左向右的尝试模型
• 可变参数有两个当前决策的位置以及剩余的步数
• 子过程情况讨论的时候分为3种，开头位置，结束位置及普遍位置；rest=0时分为两种情况要么为0要么为1

核心代码：

递归代码：

public static int ways(int N, int start, int aim, int K) {
    if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        return -1;
    }
    return process(start, K, aim, N);
}
public static int process(int index, int rest, int aim, int N) {
    if (rest == 0) {
        return index == aim ? 1 : 0;
    }
    if (index == 1) {
        return process(2, rest - 1, aim, N);
    }
    if (index == N) {
        return process(N - 1, rest - 1, aim, N);
    }
    return process(index - 1, rest - 1, aim, N) + process(index + 1, rest - 1, aim, N);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

dp代码：

public static int dp(int N, int start, int aim, int K) {
    if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        return -1;
    }
    int[][] dp = new int[N + 1][K + 1];
    dp[aim][0] = 1;
    for (int rest = 1; rest <= K; rest++) {
        dp[1][rest] = dp[2][rest - 1];
        for (int cur = 2; cur < N; cur++) {
            dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
        }
        dp[N][rest] = dp[N - 1][rest - 1];
    }
    return dp[start][K];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

测试代码：

public static void main(String[] args) {
    System.out.println(ways(5, 2, 4, 6));
    System.out.println(dp(5, 2, 4, 6));
}
1
2
3
4

测试结果：

2.象棋跳马问题

题意：想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置，那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x，y，k
返回“马”从(0,0)位置出发，必须走k步
最后落在(x,y)上的方法数有多少种?

解题思路：

• 本题有对应的业务场景，但是我感觉解题其实是从左向右的尝试模型
• 可变参数有三个，当前决策的位置（横纵）以及剩余的步数
• 子过程情况讨论的时候分为8种，马字；rest=0时分为两种情况要么为0要么为1

核心代码：

递归代码：

public static int jump(int a, int b, int k) {
    return process(0, 0, k, a, b);
}

public static int process(int x, int y, int rest, int a, int b) {
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    if (rest == 0) {
        return (x == a && y == b) ? 1 : 0;
    }
    int ways = process(x + 2, y + 1, rest - 1, a, b);
    ways += process(x + 1, y + 2, rest - 1, a, b);
    ways += process(x - 1, y + 2, rest - 1, a, b);
    ways += process(x - 2, y + 1, rest - 1, a, b);
    ways += process(x - 2, y - 1, rest - 1, a, b);
    ways += process(x - 1, y - 2, rest - 1, a, b);
    ways += process(x + 1, y - 2, rest - 1, a, b);
    ways += process(x + 2, y - 1, rest - 1, a, b);
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

dp代码：

public static int dp(int a, int b, int k) {
    int[][][] dp = new int[10][9][k + 1];
    dp[a][b][0] = 1;
    for (int rest = 1; rest <= k; rest++) {
        for (int x = 0; x < 10; x++) {
            for (int y = 0; y < 9; y++) {
                int ways = pick(dp, x + 2, y + 1, rest - 1);
                ways += pick(dp, x + 1, y + 2, rest - 1);
                ways += pick(dp, x - 1, y + 2, rest - 1);
                ways += pick(dp, x - 2, y + 1, rest - 1);
                ways += pick(dp, x - 2, y - 1, rest - 1);
                ways += pick(dp, x - 1, y - 2, rest - 1);
                ways += pick(dp, x + 1, y - 2, rest - 1);
                ways += pick(dp, x + 2, y - 1, rest - 1);
                dp[x][y][rest] = ways;
            }
        }
    }
    return dp[0][0][k];
}

public static int pick(int[][][] dp, int x, int y, int rest) {
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    return dp[x][y][rest];
}
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

测试代码：

public static void main(String[] args) {
    int x = 7;
    int y = 7;
    int step = 10;
    System.out.println(jump(x, y, step));

    System.out.println(dp(x, y, step));
}
1
2
3
4
5
6
7
8

测试结果：

3.N皇后问题

题意：N皇后问题是指在N*N的棋盘上要摆N个皇后，
要求任何两个皇后不同行、不同列， 也不在同一条斜线上
给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1
n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
n=8，返回92

解题思路：

• …没有好办法，感觉目前只掌握暴力尝试吧

核心代码：

public static int num1(int n) {
    if (n < 1) {
        return 0;
    }
    int[] record = new int[n];
    return process1(0, record, n);
}

// 当前来到i行，一共是0~N-1行
// 在i行上放皇后，所有列都尝试
// 必须要保证跟之前所有的皇后不打架
// int[] record record[x] = y 之前的第x行的皇后，放在了y列上
// 返回：不关心i以上发生了什么，i.... 后续有多少合法的方法数
public static int process1(int i, int[] record, int n) {
    if (i == n) {
        return 1;
    }
    int res = 0;
    // i行的皇后，放哪一列呢？j列，
    for (int j = 0; j < n; j++) {
        if (isValid(record, i, j)) {
            record[i] = j;
            res += process1(i + 1, record, n);
        }
    }
    return res;
}

public static boolean isValid(int[] record, int i, int j) {
    // 0..i-1
    for (int k = 0; k < i; k++) {
        if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
            return false;
        }
    }
    return true;
}
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

4.喝咖啡（放弃）

题意：给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间
给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡
只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
假设所有人拿到咖啡之后立刻喝干净，
返回从开始等到所有咖啡机变干净的最短时间
三个参数：int[] arr、int N，int a、int b

解题思路：

核心代码：

测试代码：

测试结果：

业务限制尝试模型总结

改写Dp：

• 分析清楚业务中的参数，确定范围
• 套用其他三种尝试模型

例题总结：

• 机器人行进问题——1,7，中间，rest为0，两个可变参数
• 象棋跳马问题——三个可变参数，走马的八种情况；参数的范围和方向
• N皇后问题——目前只掌握题意和递归
• 喝咖啡——放弃…