动态规划总结及套路【4】

旧城等待， 2024-04-06 10:16 73阅读 0赞

## 动态规划总结及套路【4】 ##

### 1 基本题目 ###

#### 1.1 较小集合的累加和 ####

![在这里插入图片描述][edf351bca2ce46d19cfa87ce43315efd.png]

##### 1.1.1 尝试方法 #####

/**
     * 给定一个数组arr,将arr分为两个集合，让两个集合的累加和尽量接近
     * @param arr
     * @return 返回较小集合的累加和
     */
    public static int right(int[] arr){
        
        if(arr == null || arr.length < 2){
        
            return 0;
        }
        int sum = 0;
        for(int num : arr){
        
            sum += num;
        }
        return process(arr, 0, sum / 2);
    }
    
    /**
     * 
     * @param arr 所给集合arr
     * @param i   当前位置为i
     * @param rest 目标累加和rest
     * @return 返回arr[i...]累加和尽量接近rest的值
     */
    public static int process(int[] arr, int i, int rest){
        
        if(i == arr.length){
        
            //来到了数组末尾，没有数可选
            return 0;
        } else {
        
            //不选择arr[i]数
            int p1 = process(arr, i+1, rest);
            int p2 = -1;
            if(arr[i] <= rest){
        
                //选择了arr[i]，累加和需要加上
                p2 = arr[i] + process(arr, i+1, rest - arr[i]);
            }
            return Math.max(p1, p2);
        }
    }

##### 1.1.2 改为动态规划 #####

`一定要根据递归找出依赖`：

//p2 = arr[i] + process(arr, i+1, rest - arr[i]);
    //i, rest位置上的值依赖i+1, rest - arr[i]的值

public static int dp2(int[] arr){
        
        if(arr == null || arr.length < 2){
        
            return 0;
        }
        int sum = 0;
        for(int num : arr){
        
            sum += num;
        }
        int aim = sum / 2;
        int N = arr.length;
        //最接近N，可以取到N，因此长度为N+1
        //index 行
        //aim 列
        int[][] dp = new int[N+1][aim+1];
        //p2 = arr[i] + process(arr, i+1, rest - arr[i]);
        //i, rest位置上的值依赖i+1, rest - arr[i]的值
        //一定要根据递归找出依赖
        for(int index = N - 1; index >= 0; index--){
        
            for(int rest = aim; rest >= 0; rest--){
        
                //不选择index位置上的数
                int p1 = dp[index+1][rest];
                //选择index位置上的数
                int p2 = -1;
                if(arr[index] <= rest){
        
                    p2 = arr[index] + dp[index+1][rest - arr[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][aim];
    }

#### 1.2 较小集合的累加和2 ####

![在这里插入图片描述][17fdfed4e99d4665af7d5ce5e9e757e3.png]

##### 1.2.1 尝试 #####

//返回较小集合的累加和
    //两个集合长度要一样多，如果arr的length为奇数，两个集合长度只差1
    public static int right(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
        
            sum += num;
        }
        return Math.max(process(arr, 0, (arr.length + 1) >> 1, sum / 2), process(arr, 0, arr.length / 2, sum / 2));
    }
    
    /**
     *
     * @param arr
     * @param i 当前来到arr的位置
     * @param picks 目标集合长度
     * @param rest 累加和小于等于rest，最接近rest
     * @return arr[i....]自由选择，挑选的个数一定要是picks个，累加和<=rest, 离rest最近的返回
     */
    public static int process(int[] arr, int i, int picks, int rest) {
        
        if (i == arr.length) {
        
            //看看是否满足长度限制
            return picks == 0 ? 0 : -1;
        } else {
        
            int p1 = process(arr, i + 1, picks, rest);
            int p2 = -1;
            int next = -1;
            if (arr[i] <= rest) {
        
                next = process(arr, i + 1, picks - 1, rest - arr[i]);
            }
            if(next != -1){
        
                p2 = next + arr[i];
            }
            return Math.max(p1, p2);
        }
    }

##### 1.2.2 动态规划 #####

public static int dp3(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
        
            sum += num;
        }
        int N = arr.length;
        int aim = sum / 2;
        //集合长度
        int M = (N + 1) / 2;
        //X:index
        //M:集合长度 > picks
        //aim:rest
        int[][][] dp = new int[N + 1][M + 1][aim + 1];
        //初始化全部置为：-1，无效值
        for (int i = 0; i <= N; i++) {
        
            for (int j = 0; j <= M; j++) {
        
                for (int k = 0; k <= aim; k++) {
        
                    dp[i][j][k] = -1;
                }
            }
        }
        //根据递归填写对应值：i==arr.length    >   picks == 0 ? 0 : -1
        for (int rest = 0; rest <= aim; rest++) {
        
            dp[N][0][rest] = 0;
        }
        //index[根据递归可以知道每层依赖下一层的值，因此需要从最底层开始填]
        for (int i = N - 1; i >= 0; i--) {
        
            //pick
            for (int pick = 0; pick <= M; pick++) {
        
                //rest
                for (int rest = 0; rest <= aim; rest++) {
        
                    //
                    int p1 = dp[i + 1][pick][rest];
                    int p2 = -1;
                    int next = -1;
                    if (pick - 1 >= 0 && arr[i] <= rest) {
        
                        next = dp[i + 1][pick - 1][rest - arr[i]];
                    }
                    if (next != -1) {
        
                        p2 = next + arr[i];
                    }
                    dp[i][pick][rest] = Math.max(p1, p2);
                }
            }
        }
        //如果arr长度为奇数，看是选择奇数个集合还是长度为偶数的集合
        if ((arr.length & 1) == 0) {
        
            //arr长度为偶数
            return dp[0][arr.length / 2][aim];
        } else {
        
            return Math.max(dp[0][(arr.length + 1) / 2][aim], dp[0][arr.length / 2][aim]);
        }
    }

#### 1.3 N皇后问题 ####

![在这里插入图片描述][a21efb2f71fb4a48a078c218b621d88e.png]

##### 1.3.1 尝试 #####

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;
    }
    
    //皇后放在i行j列
    public static boolean isValid(int[] record, int i, int j) {
        
        //0..i-1
        for (int k = 0; k < i; k++) {
        
            // j == record[k] 判断列是否合法
            // Math.abs(record[k] - j) == Math.abs(i - k) 是否在同一条斜线上
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
        
                return false;
            }
        }
        return true;
    }

##### 1.3.2 常数时间优化【列影响、左下、右下影响】 #####

//请不要超过32皇后问题
    public static int num2(int n){
        
        if(n < 1 || n > 32){
        
            return 0;
        }
        //如果是13皇后的问题，limit最右13个1，其他都是0
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }
    
    //7皇后问题
    //limit: 0....0 1 1 1 1 1 1 1
    //之前皇后的列影响：colLim
    //之前皇后的左下对角线影响：leftDiaLim
    //之前皇后的右下对角线影响：rightDiaLim
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim){
        
        if(colLim == limit){
        
            return 1;
        }
        //pos中所有是1的位置，是可以去尝试放置皇后的位置
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;
        int res = 0;
        while(pos != 0){
        
            //每次取出最右侧的1【先打散再聚合再&】
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

### 2 动态规划总结 ###

我们常见的动态规划，都可以通过暴力递归修改得到。

*  什么暴力递归可以继续优化？

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

*  暴力递归与动态规划关系

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

*  面试题与动态规划的关系

> 解决一个问题，可能有很多尝试方法  
> 可能在很多尝试中，又有若干个尝试方法有动态规划的方式  
> 一个问题 可能有 若干种动态规划的解法

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

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

*  `**面试中设计暴力递归过程的原则**`

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

*  知道了面试中设计暴力递归过程的原则，然后呢？

> 我们一定要逼自己找到不违反原则情况下的暴力尝试！  
> 如果我们找到的暴力尝试，不符合原则，马上舍弃，寻找新的！！  
> 如果某个题目突破了设计原则，那么该题一定极难，在面试中出现概率低于5%！

*  `常见的4种尝试模型`

> 1.  从左往右的尝试模型：背包问题
> 2.  范围上的尝试模型
> 3.  多样本对应的尝试模型【多样本位置全对应】
> 4.  寻找业务限制的尝试模型

*  如何分析有没有重复解

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

*  `暴力递归到动态规划的套路`

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

*  动态规划的进一步优化

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

[edf351bca2ce46d19cfa87ce43315efd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f0e3c734d4244df880dea558754d64a8.png
[17fdfed4e99d4665af7d5ce5e9e757e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b9a59b5c902e47949816cc3fa1a55ce4.png
[a21efb2f71fb4a48a078c218b621d88e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/067d2eeee8c847cf8aae7c7074055474.png