【算法&数据结构体系篇class18】：暴力递归到记忆化搜索到动态规划

朴灿烈づ我的快乐病毒、 2024-03-25 20:11 49阅读 0赞

### 一、什么暴力递归可以继续优化？ ###

> 有重复调用同一个子问题的解，这种递归可以优化  
>   
> 如果每一个子问题都是不同的解，无法优化也不用优化

### 二、暴力递归和动态规划的关系 ###

> 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划  
>   
> 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归  
>   
> 但不是所有的暴力递归，都一定对应着动态规划

### 三、如何找到某个问题的动态规划方式？ ###

> 1）设计暴力递归：重要原则+4种常见尝试模型！重点！  
>   
> 2）分析有没有重复解：套路解决  
>   
> 3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决  
>   
> 4）看看能否继续优化：套路解决

### 四、设计暴力递归过程的原则 ###

> 1）每一个可变参数的类型，一定不要比int类型更加复杂  
>   
> 2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数  
>   
> 3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可  
>   
> 4）可变参数的个数，能少则少

### 五、常见的4种尝试模型 ###

> 1）从左往右的尝试模型  
>   
> 2）范围上的尝试模型  
>   
> 3）多样本位置全对应的尝试模型  
>   
> 4）寻找业务限制的尝试模型

### 六、如何分析有没有重复解 ###

> 列出调用过程，可以只列出前几层  
>   
> 有没有重复解，一看便知

### 七、暴力递归到动态规划的套路 ###

> 1）你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用  
> 2）找到哪些参数的变化会影响返回值，对每一个列出变化范围  
> 3）参数间的所有的组合数量，意味着表大小  
> 4）记忆化搜索的方法就是傻缓存，非常容易得到  
> 5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解  
> 6）对于有枚举行为的决策过程，进一步优化

### 八、动态规划的进一步优化 ###

> 1）空间压缩  
>   
> 2）状态化简  
>   
> 3）四边形不等式  
>   
> 4）其他优化技巧

### 九、题目：机器人移动 ###

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

package class18;
    
    /**
     * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
     * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
     * 如果机器人来到1位置，那么下一步只能往右来到2位置；
     * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
     * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
     * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
     * 给定四个参数 N、M(cur)、K(rest)、P(aim)，返回方法数。
     */
    public class RobotWalk {
        //方法一：暴力递归
        public static int ways1(int N, int start, int aim, int K) {
            //边界判断 N至少要2个 机器人才能移动。 start开始位置和aim目标位置 范围在1-N，K步要大于0
            if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
                //越界输入 直接返回-1
                return -1;
            }
            //调用递归函数，返回符合的从start移动k步到aim的次数
            return process1(start,K,aim,N);
        }
    
        /**
         *
         * @param cur  机器人当前来到的位置cur
         * @param rest 机器人还有rest步要走
         * @param aim  最终要达到的目标位置aim
         * @param N    一共有N个位置
         */
        public static int process1(int cur, int rest, int aim, int N){
            if(rest == 0){
                //base case:当步数都走完了的时候 判断cur当前位置是否来到aim 是则返回1种，否则就是0
                return cur == aim ? 1: 0;
            }
            //如果还有剩余步数 rest >0 那么判断几种情况的移动
            //当前cur在1位置时，只有向右+1 向左会越界 来到2  步数-1
            if(cur == 1){
                return process1(2,rest-1,aim,N);
            }
            //当前cur在N位置时，只能向左 -1 向右会越界  步数-1
            if(cur == N){
                return process1(N-1, rest - 1,aim,N);
            }
            //如果不在1 N 在中间 那么既可以向左 也可以向右 那么就表示有两种情况 返回就将两者相加
            return process1(cur-1,rest-1,aim,N) + process1(cur+1,rest-1,aim,N);
        }
    
    
        //优化方法二：添加缓存表 自顶向下的动态规划  也叫 记忆化搜索
        public static int ways2(int N,int start, int aim, int K){
            //边界判断 N至少要2个 机器人才能移动。 start开始位置和aim目标位置 范围在1-N，K步要大于0
            if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
                //越界输入 直接返回-1
                return -1;
            }
            //方法一中 只跟cur rest相关 目标节点aim  n位置数 整个过程不影响
            //cur 当前位置范围是 1-N   rest 剩余步数 范围是 0-K
            //定义 二维数组 cur*rest 范围来保存这两个值的全部结果，作为缓存表作用 长度N+1 K+1 dp[0]行不处理 从1-N行处理即可
            int[][] dp = new int[N+1][K+1];
            for(int i = 0;i <= N;i++){
                for(int j = 0; j <= K;j++){
                    //初始化赋值-1 表示还没访问到的位置
                    dp[i][j] = -1;
                }
            }
            //从start开始位置移动K步 来到aim目标位置 传递dp保存访问结果 减少遍历次数 缓存表
            return process2(start,K,aim,N,dp);
        }
    
        public static int process2(int cur, int rest, int aim, int N, int[][]dp){
            //如果当前位置cur 剩余步数rest 得到的结果不是-1 就直接返回
            if(dp[cur][rest] != -1){
                //如果cur rest不是-1 说明已经访问过计算过结果了，直接返回 不用再计算
                return dp[cur][rest];
            }
            //定义一个结果集 用来返回
            int ans = 0;
            //情况1 剩余步数为0时
            if(rest == 0){
                //步数走完 当cur位置来到aim目标位置 说明符合题意次数 返回1  否则返回0
                ans = cur == aim ? 1 :0;
            }else if(cur == 1){
                //情况2 如果当前位置在1 还有剩余步数 那么只能向右走来到2 步数-1 赋值给ans
                ans = process2(2,rest-1,aim,N,dp);
            }else if(cur == N){
                //情况3 剩余步数 cur在N 只能往左走
                ans = process2(N-1,rest-1,aim ,N,dp);
            }else{
                //情况4 不在头尾 那么就在中间 可以往左也可以往右
                ans = process2(cur+1,rest-1,aim,N,dp) + process2(cur-1,rest-1,aim,N,dp);
            }
            //赋值完成后，最后返回前 需要进行对缓存表的赋值
            dp[cur][rest] = ans;
            return ans;
        }
    
        //优化方法三：最终版动态规划 通过前面的递归加缓存表可以得到结果都是存放到一个二维数组
        //而目标就是根据前面的各种情况，填充这张表dp[N+1][K+1]，而结果返回的 根据题意要求cur当前位置 走了K步 就是dp[cur][rest]
        public static int ways3(int N,int start, int aim, int K){
            //边界判断 N至少要2个 机器人才能移动。 start开始位置和aim目标位置 范围在1-N，K步要大于0
            if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
                //越界输入 直接返回-1
                return -1;
            }
            //方法一中 只跟cur rest相关 目标节点aim  n位置数 整个过程不影响
            //cur 当前位置范围是 1-N   rest 剩余步数 范围是 0-K
            //定义 二维数组 cur*rest 范围来保存这两个值的全部结果，作为缓存表作用 长度N+1 K+1 dp[0]行不处理 从1-N行处理即可
            int[][] dp = new int[N+1][K+1];   //默认值都是0
            //情况1 确定base case 当rest为0 时  只有cur==aim 值则为1 否则为0
            dp[aim][0] = 1;      //cur移动位置是行数，cur == aim 就在第aim行 第0列表示 rest没有剩余步数 此时值为1 该列其他位置都是0
            //当前rest剩余步数不为0时 则有多种情况
            for(int rest = 1; rest <= K; rest++) {
                //情况2 当cur位置来到1 时 机器人只能向右移动 来到2 也就是向下一行移动 并且剩余步数-1 向左一列移动 也就是依赖 左下位置的值
                dp[1][rest] = dp[2][rest-1];
    
                //情况3 当cur位置来到N 时 机器人只能向左移动 来到N-1 也就是向上一行移动 并且剩余步数-1 向左一列移动 也就是依赖 左上位置的值
                dp[N][rest] = dp[N-1][rest-1];
    
                //情况4 cur 不在1  N  机器人可以向左 向右移动 去到cur-1 cur+1 也就是上下一行的位置 剩余步数-1 左移一列 也就是以来 左下和左上位置的值
                for(int cur = 2; cur < N;cur++){
                    dp[cur][rest] = dp[cur-1][rest-1] + dp[cur+1][rest-1];
                }
            }
            //把二维数组填充完成 最后题意要求的位置 就是在start位置到K步的值
            return dp[start][K];
        }
    
        public static void main(String[] args) {
            System.out.println(ways1(5, 2, 4, 6));
            System.out.println(ways2(5, 2, 4, 6));
            System.out.println(ways3(5, 2, 4, 6));
        }
    }

### 十、题目：抽纸牌 ###

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

package class18;
    
    /**
     * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
     * 玩家A和玩家B依次拿走每张纸牌
     * 规定玩家A先拿，玩家B后拿
     * 但是每个玩家每次只能拿走最左或最右的纸牌
     * 玩家A和玩家B都绝顶聪明
     * 请返回最后获胜者的分数。
     */
    public class CardsInLine {
        //方法一：暴力递归 根据题意规则来写递归逻辑
        public static int win1(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;   //base case 数组没有纸牌了都会被拿走时 为空 就返回0 分数
            }
            //调用 玩家A先拿者函数，返回玩家A的获胜分数
            //从数组开始0-最后一个索引 开始递归
            int first = f1(arr, 0, arr.length-1);
            //调用 玩家B后拿者函数，返回玩家B的获胜分数
            int second = g1(arr, 0, arr.length-1);
            //最后返回分数较大者
            return Math.max(first, second);
        }
    
        //玩家A先拿者 在数组L-R中获得的最好分数返回
        public static int f1(int[] arr, int L, int R) {
            if (L == R) {
                //base case 如果当前数组只有一个，那么玩家A是先手拿，那就返回当前该位置的分数
                return arr[L];
            }
            //如果不止一个 那么根据题意 可以从最左 最右 取牌
            //情况1：从左边取牌，那么剩下的就是L+1,R的牌 给玩家B后手拿 返回该情况的分数
            int p1 = arr[L] + g1(arr, L + 1, R);
            //情况2: 从右边取牌，那么剩下的就是L,R-1的牌 给玩家B后手拿 返回该情况的分数
            int p2 = arr[R] + g1(arr, L, R - 1);
            //两种情况，根据题意 玩家都是绝顶聪明 就会取两种情况较大值 作为自己的分数
            return Math.max(p1, p2);
        }
    
        //玩家B后拿者 在数组L-R中获得的最好分数返回
        public static int g1(int[] arr, int L, int R) {
            if (L == R) {
                return 0; //base case 如果当前只剩一张，因为这是玩家B后拿者，剩一张肯定是给玩家A先手拿了 所以就返回0
            }
            //如果不止一个，那么就判断情况
            //情况1 先手拿了L位置的牌，那么接着后手玩家B只能从 L-1,R中拿尽量分数最高的 就回到调用f1函数 该函数就是取分数最高的判断
            //相当与此时玩家B来到了玩家A的阶段
            int p1 = f1(arr, L + 1, R);
            //情况2 先手拿了R位置的牌，那么接着后手玩家B只能从 L,R-1中拿尽量分数最高的 就回到调用f1函数 该函数就是取分数最高的判断
            int p2 = f1(arr, L, R - 1);
            //情况分析完后，最后要返回玩家B后拿的最高分数，这里要考虑 取两者情况的较小值，因为f1()先手调用函数是会取最高分数的，而给到后
            //手时是分给后手各种情况中尽量少的分 所以返回两者较小值,这是被迫返回较小 因为题意要求玩家都是绝顶聪明，那么先手肯定是将分数高的给
            //自己，而给后手预留的就是尽量小的分数
            return Math.min(p1, p2);
        }
    
        //方法二：优化 缓存表  通过暴力递归函数的参数确定一个数组范围来填充结果
        public static int win2(int[] arr){
            if (arr == null || arr.length == 0) {
                return 0;   //base case 数组没有纸牌了都会被拿走时 为空 就返回0 分数
            }
            //根据L R的递归参数 定义一个二维数组 N行N列 N为arr的长度,注意这里是两个递归函数
            //分别定义两个二维数组 分开处理
            int N = arr.length;
            int[][] fmap = new int[N][N];
            int[][] gmap = new int[N][N];
            //初始化-1
            for(int i =0; i < N; i++){
                for(int j = 0; j < N; j++){
                    fmap[i][j] = -1;
                    gmap[i][j] = -1;
                }
            }
            //调用玩家A先手拿牌返回最好分数
            int first = f2(arr,0,N-1,fmap,gmap);
            //调用玩家B后手拿牌返回最好分数
            int second = g2(arr,0,N-1,fmap,gmap);
            //返回两者较大者
            return Math.max(first,second);
        }
    
        //玩家A先拿者 在数组L-R中获得的最好分数返回
        public static int f2(int[] arr, int L, int R,int[][]fmap, int[][]gmap){
            if(fmap[L][R] != -1){
                return fmap[L][R];  //base case:对应先拿玩家的二维数组 如果该位置不为-1 说明已经访问计算过 直接返回
            }
            //如果为-1 那么就表示首次计算访问 定义一个结果保存分数
            int ans = 0;
            //如果只有一个牌,先拿玩家肯定就会要这张牌 把值赋给ans
            if(L == R){
                ans = arr[L];
            }else {
                //如果不止一个牌 那么就可以取左边的牌 然后接着让后手玩家取L+1,R区间的牌的最好分数
                int p1 = arr[L] + g2(arr, L+1,R,fmap,gmap);
                //也可以取右边的牌....后手玩家取L,R-1
                int p2 = arr[R] + g2(arr,L,R-1,fmap,gmap);
                //那么就会取两者情况的较大者赋值给ans
                ans = Math.max(p1,p2);
            }
            //最后返回ans,之前先把结果记录到fmap表中 后续就不需要再递归计算 直接取值返回
            fmap[L][R] = ans;
            return ans;
        }
    
        //玩家B后拿者 在数组L-R中获得的最好分数返回
        public static int g2(int[] arr, int L, int R, int[][]fmap, int[][]gmap){
            if(gmap[L][R] != -1){
                return gmap[L][R]; //base case:如果后者玩家表中已经访问计算过，那么就直接返回
            }
            //表为-1 说明首次访问 先定义一个结果
            int ans = 0;
            //按情况判断 如果只剩一张牌 那么这张牌只能给先手玩家取 而当前后手玩家则值为0
            if(L == R){
                ans = 0;
            }else{
                //如果不止一张，那么就是如果前手取L 后手只能从L+1,R取,而L被先手玩家取了 不能累加
                int p1 = f2(arr,L+1,R,fmap,gmap);
                //也可以前手取R  后手就是L,R-1范围取最好分数
                int p2 = f2(arr, L, R-1,fmap,gmap);
                //因为先手玩家聪明绝顶，肯定会选分数高的，然后剩下的会尽量返回较小的给后手 所以取两者情况较小值
                ans = Math.min(p1,p2);
            }
            //最后返回ans 前先给缓存表赋值
            gmap[L][R] = ans;
            return ans;
        }
    
    
        //方法三：最终动态规划  从前面找依赖 填充好二维表 最好直接返回
        public static int win3(int[] arr){
            if (arr == null || arr.length == 0) {
                return 0;   //base case 数组没有纸牌了都会被拿走时 为空 就返回0 分数
            }
            //根据L R的递归参数 定义一个二维数组 N行N列 N为arr的长度,注意这里是两个递归函数
            //分别定义两个二维数组 分开处理
            int N = arr.length;
            int[][] fmap = new int[N][N];
            int[][] gmap = new int[N][N];
            //初始化 根据前面情况L == R时，fmap玩家缓存表中值就是arr[L] 也就是二维数组的对角线值依次都是数组对应的下标值
            for(int i = 0; i< N;i++){
                fmap[i][i] = arr[i];
            }
            //而gmap玩家缓存表 L==R时 赋值的时0 数组初始值都是0 所以不用再赋值处理
            //接着判断情况 L <= R 才是正确的边界 左边不会大于右边 二维数组中 左下三角区就不需赋值 只需要关注右上三角区
            //看到如果不止一张牌时，先手玩家当前位置fmap[L][R] 它依赖的是arr[L] 或者arr[R] 以及后手玩家g函数gmap缓存表中 L+1,R  L,R-1 也就是对应gmap[L][R]的下一个位置和左一个位置
            //通过这个规律我们可以这样赋值两个表：
            // 第一列fmap[0][0]是对角线前面已经赋值过，那么再往右第二列，依次再往右下的对角线，进行赋值：
            //来到fmap[0][1] 其依赖的就是arr[L]+对应gmap[0][1]的gmap[1][1]    arr[R]+对应gmap[0][1]的gmap[0][0] 两者的较大值
    
    
            //所以根据这个规则 外层循环就是遍历 1-N列 每次都完成对应的对角线位置值，每次就是往右下位置，直到N列越界 就再从N=2开始遍历其右下位置整条对角线
            for(int startCol = 1; startCol < N; startCol++){
                //对角线startCol 0位置前面已经处理 从第一列开始
                //定义该次对角线的索引位置进行移动,每次都是从第一行开始的往右下遍历
                int L = 0;
                int R = startCol;
                while(R < N){
                    //越界判断 当R列到N时就越界 而行是肯定不会先与列越界的 因为是在对角线上方，R列到最大N时，L行最多就是N-1行
                    //开始给两个缓存表填充值 根据前面分析的规律
                    //先手玩家 缓存表 当L!=R是分两者情况取最大值 取L左边的牌值加上后手玩家中L-1,R区间的牌值，     取R则加后手玩家L,R-1的牌
                    fmap[L][R] = Math.max(arr[L]+gmap[L+1][R],arr[R]+gmap[L][R-1]);
                    gmap[L][R] = Math.min(fmap[L+1][R],fmap[L][R-1]); //后手玩家同理 取前手玩家剩余的牌两者取最小
    
                    //然后接着往右下位置去一一赋值
                    L++;
                    R++;
                }
            }
            //最后缓存表都填充好数据 ，最后要返回的就是先手玩家0,N-1 已经后手玩家0,N-1的较大值
            return Math.max(fmap[0][N-1],gmap[0][N-1]);
        }
    
        public static void main(String[] args) {
            int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
            System.out.println(win1(arr));
            System.out.println(win2(arr));
            System.out.println(win3(arr));
    
        }
    
    }