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

末蓝、 2024-03-16 10:01 67阅读 0赞

## 算法|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);
    }

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];
    }

**测试代码：**

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

**测试结果：**![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ItKKrxD0-1685262047457)(F:\\typora插图\\image-20230528145502054.png)\]][img-ItKKrxD0-1685262047457_F_typora_image-20230528145502054.png]

### 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;
    }

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];
    }

**测试代码：**

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));
    }

**测试结果：**![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OQlfbb28-1685262047458)(F:\\typora插图\\image-20230528150400859.png)\]][img-OQlfbb28-1685262047458_F_typora_image-20230528150400859.png]

### 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;
    }

### 4.喝咖啡（放弃） ###

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

**解题思路：**

**核心代码：**

**测试代码：**

**测试结果：**

### 业务限制尝试模型总结 ###

**改写Dp：**

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

**例题总结：**

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

[img-ItKKrxD0-1685262047457_F_typora_image-20230528145502054.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ba35268306704c5abbc0d61081e53c33.png
[img-OQlfbb28-1685262047458_F_typora_image-20230528150400859.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/5f51bbbdd82e4ff993574f9b55d9b919.png