左神提升6：暴力递归改动态规划

超、凢脫俗 2022-09-10 07:09 189阅读 0赞

## 内容 ##

讲述暴力递归和动态规划的关系 =》去重的过程

记忆化搜索 **傻缓存**

动态规划都可以由暴力递归改进过来，解决动态规划的套路

常见的尝试模型

设计尝试过程的原则

本节是暴力递归到动态规划的总纲（很重要）

后续的课都是在讲述这一系列的套路

1、尝试=》 分辨出来所有的参数，找到所有的可变参数以及固定的值（边界）
    2、可变参数的组合是什么，表大小根据可变参数的变化范围来确定
    3、已知固定位置的依赖，有具体参数的例子（范围的两端）
    4、知道在表中的最终想要的位置，baseCase固定的行列（确定好baseCase）
    5、分析任意位置的依赖

## 题目一：机器人找位置 ##

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

### 1）cache 方法： ###

使用HashMap来存储当前的状态

public static void main(String[] args) {
        
        System.out.println(ways1(5, 2, 4, 6));
    }
    
    public static int ways1(int N, int start, int aim, int K) {
        
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        
            return -1;
        }
        HashMap<String, Integer> cache = new HashMap<>();
    
        return process(start, K, aim, N, cache);
    }
    
    // 机器人还有rest步需要去走，
    // 最终的目标是aim，
    // 有哪些位置？1~N
    public static int process(int cur, int res, int aim, int N, HashMap<String, Integer> cache) {
        
        String key = String.valueOf(cur) + "_" + String.valueOf(res);
        if (cache.containsKey(key)) {
        
            return cache.get(key);
        }
        // baseCase
        int ans = 0;
        if (res == 0) {
        
            ans = cur == aim ? 1 : 0;
            cache.put(key, ans);
            return ans;
        }
        // 边界情况
        if (cur == 1) {
        
            ans = process(cur + 1, res - 1, aim, N, cache);
            cache.put(key, ans);
            return ans;
        }
        if (cur == N) {
        
            ans = process(cur - 1, res - 1, aim, N, cache);
            cache.put(key, ans);
            return ans;
        }
        // 任意情况
        ans = process(cur - 1, res - 1, aim, N, cache)
                + process(cur + 1, res - 1, aim, N, cache);
        cache.put(key, ans);
        return ans;
    }

### 2）cache化为数组 ###

修改cache为指定大小的数组，空间复杂度降下来了

// 机器人还有rest步需要去走，
    // 最终的目标是aim，
    // 有哪些位置？1~N
    public static int process(int cur, int res, int aim, int N, int[][] cache) {
        
        if (cache[cur][res] != 0 ) {
        
            return cache[cur][res];
        }
        // baseCase
        int ans = 0;
        if (res == 0) {
        
            ans = cur == aim ? 1 : 0;
            cache[cur][res] = ans;
            return ans;
        }
        // 边界情况
        if (cur == 1) {
        
            ans = process(cur + 1, res - 1, aim, N, cache);
            cache[cur][res] = ans;
            return ans;
        }
        if (cur == N) {
        
            ans = process(cur - 1, res - 1, aim, N, cache);
            cache[cur][res] = ans;
            return ans;
        }
        // 任意情况
        ans = process(cur - 1, res - 1, aim, N, cache)
                + process(cur + 1, res - 1, aim, N, cache);
        cache[cur][res] = ans;
        return ans;
    }

### 3）继续简化 ###

public class Test {
        
        public static void main(String[] args) {
        
            System.out.println(ways1(5, 2, 4, 6));
        }
    
        public static int ways1(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 + 2][K + 1];
            for (int i = 0; i <= N; i++) {
        
                for (int j = 0; j <= K; j++) {
        
                    dp[i][j] = -1;
                }
            }
            return process(start, K, aim, N, dp);
        }
    
        // 机器人还有rest步需要去走，
        // 最终的目标是aim，
        // 有哪些位置？1~N
        public static int process(int cur, int rest, int aim, int N, int[][] dp) {
        
            if (dp[cur][rest] != -1) {
        
                return dp[cur][rest];
            }
    
            int ans = 0;
            if (rest == 0) {
        
                ans = cur == aim ? 1 : 0;
            } else if (cur == 1) {
        
                ans = process(2, rest - 1, aim, N, dp);
            } else if (cur == N) {
        
                ans = process(N - 1, rest - 1, aim, N, dp);
            } else {
        
                ans = process(cur - 1, rest - 1, aim, N, dp)
                        + process(cur + 1, rest - 1, aim, N, dp);
            }
            dp[cur][rest] = ans;
            return ans;
        }
    }

### 4）dp过程 ###

画出table表：  
动态规划是直接把暴力递归的思路直接架空，拿出所对应的确定的值进行计算

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

public class Test {
        
        public static void main(String[] args) {
        
    //        K:剩余步数
            System.out.println(process(2, 4, 6, 5));
        }
    
        // 机器人还有rest步需要去走，
        // 最终的目标是aim，
        // 有哪些位置？1~N
        public static int process(int start, int aim, int K, int N) {
        
            if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        
                return -1;
            }
            int[][] dp = new int[N + 1][K + 1];
    
            // cur已经到aim，而剩余步数也为0了
            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];
        }
    }

## 题目二：抽牌博弈 ##

给定一个整型数组arr，代表数值不同的纸牌排成一条线  
玩家A和玩家B依次拿走每张纸牌  
规定玩家A先拿，玩家B后拿  
但是每个玩家每次只能拿走最左或最右的纸牌  
玩家A和玩家B都绝顶聪明  
请返回最后获胜者的分数

### 题解： ###

// 根据规则，返回获胜者的分数
    	public static int win1(int[] arr) {
        
    		if (arr == null || arr.length == 0) {
        
    			return 0;
    		}
    		int first = f1(arr, 0, arr.length - 1);
    		int second = g1(arr, 0, arr.length - 1);
    		return Math.max(first, second);
    	}
    
    	// arr[L..R]，先手获得的最好分数返回
    	public static int f1(int[] arr, int L, int R) {
        
    		if (L == R) {
        
    			return arr[L];
    		}
    		int p1 = arr[L] + g1(arr, L + 1, R);
    		int p2 = arr[R] + g1(arr, L, R - 1);
    		return Math.max(p1, p2);
    	}
    
    	// // arr[L..R]，后手获得的最好分数返回
    	public static int g1(int[] arr, int L, int R) {
        
    		if (L == R) {
        
    			return 0;
    		}
    		int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
    		int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
    		return Math.min(p1, p2);
    	}

## 题目三：象棋问题： ##

### 暴力方法： ###

public class JumpHorse{
        
        public static void main(String[] args) {
        
            int enda = 5;
            int endb = 7;
            int rest = 10;
            System.out.println(process(0, 0, enda, endb, rest));
        }
    
        public static int process(int x, int y, int enda, int endb, int rest) {
        
            if (x < 0 || x > 9 || y < 0 || y > 8) {
        
                return 0;
            }
            if (rest == 0) {
        
                return x == enda && y == endb ? 1 : 0;
            }
            int res = 0;
            res = process(x+2, y+1, enda, endb, rest-1) +
                    process(x+1, y+2, enda, endb, rest-1) +
                    process(x-1, y-2, enda, endb, rest-1) +
                    process(x-2, y-1, enda, endb, rest-1) +
                    process(x-1, y+2, enda, endb, rest-1) +
                    process(x+1, y-2, enda, endb, rest-1) +
                    process(x+2, y-1, enda, endb, rest-1) +
                    process(x-2, y+1, enda, endb, rest-1);
            return res;
        }
    }

### 改动态规划： ###

public class JumpHorse{
        
        public static void main(String[] args) {
        
            int enda = 5;
            int endb = 7;
            int rest = 10;
            System.out.println(waysdp(enda, endb, rest));
        }
        public static int waysdp(int a, int b, int s) {
        
            int[][][] dp = new int[10][9][s + 1];
            dp[a][b][0] = 1;
            for (int step = 1; step <= s; step++) {
         // 按层来
                for (int i = 0; i < 10; i++) {
        
                    for (int j = 0; j < 9; j++) {
        
                        dp[i][j][step] = getValue(dp, i - 2, j + 1, step - 1) + getValue(dp, i - 1, j + 2, step - 1)
                                + getValue(dp, i + 1, j + 2, step - 1) + getValue(dp, i + 2, j + 1, step - 1)
                                + getValue(dp, i + 2, j - 1, step - 1) + getValue(dp, i + 1, j - 2, step - 1)
                                + getValue(dp, i - 1, j - 2, step - 1) + getValue(dp, i - 2, j - 1, step - 1);
                    }
                }
            }
            return dp[0][0][s];
        }
        // 在dp表中，得到dp[i][j][step]的值，但如果(i，j)位置越界的话，返回0；
        public static int getValue(int[][][] dp, int i, int j, int step) {
        
            if (i < 0 || i > 9 || j < 0 || j > 8) {
        
                return 0;
            }
            return dp[i][j][step];
        }
    
    }

## 题目四、换钱的最少货币数 ##

暴力递归到动态规划题目。

### 记忆化搜索： ###

涉及到一些套路，dp的分析……

public class Test {
        
        public static void main(String[] args) {
        
            processOpen();
        }
    
        public static void processOpen() {
        
            int[] arr = new int[]{
        5, 2, 3};
            int aim = 10;
            System.out.println(process(arr, 0, aim));
        }
        
        public static int process(int[] arr, int idx, int rest) {
        
            if (idx >= arr.length) {
        
                return rest == 0 ? 1 : 0;
            }
            int sum = 0;
            for (int n = 0; n * arr[idx] <= rest; n++) {
        
                sum += process(arr, idx + 1, rest - n * arr[idx]);
            }
            return sum;
        }
    
    }

### dp优化 ###

又叫做顺序依赖，DP过程

public class xx {
        
        public static int process(int[] arr, int idx, int aim) {
        
            int[][] dp = new int[arr.length + 1][aim+1];
            dp[arr.length][0] = 1;
    
            for (int i = arr.length-1; i >= 0; i--) {
        
                for (int j = 0; j <= aim; j++) {
        
                    dp[i][j] = dp[i + 1][j];
                    if (j - arr[i] >= 0) {
        
                        dp[i][j] += dp[i][j - arr[i]];
                    }
                }
            }
            return dp[0][aim];
        }
    }

如果没有枚举过程，那么就没有必要进行dp操作，如果有枚举过程，那么可以对它做优化，《斜率优化》，可以省去重复的操作时间。

**空间压缩：**

使用一维的数据来代替二维的数据

依赖多个数据的时候，使用两个数组交替着滚动，交替使用（省空间）

1）l-》r（背包问题）

2）范围尝试：L-R（回文）

3）2样本

**尝试原则：**

1）设计尽量简单，限制可变参数为整数类型，否则可能性太大了

2）可变参数个数尽量少，

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a892cc91290c474289758bbc01618028.png