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

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

1 基本题目

1.1 较小集合的累加和

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
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
38

1.1.2 改为动态规划

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

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

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
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

1.2 较小集合的累加和2

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
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
38

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
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

1.3 N皇后问题

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
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
38
39
40

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

2 动态规划总结

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

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

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

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

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

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

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

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

1. 设计暴力递归：重要原则+4种常见模型！重点！！！

2. 分析有没有重复解：套路解决
3. 用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
4. 看看能够继续优化：套路解决

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

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） 其他优化技巧