# 第23节 暴力递归到动态规划（六）
暴力递归改动态规划步骤：
- 一定要尝试出暴力递归版本，设计暴力递归：重要原则+4种常见尝试模型
从左往右的尝试模型范围上的尝试模型多样本位置全对应的尝试模型寻找业务限制的尝试模型- 分析有无重复解
- 用记忆化搜索实现
- 分析可变参数范围
- 写出basecase程式
- 分析普遍位置依赖
- 最终推出严格表结构实现动态规划
- 继续看严格表结构是否可再优化
- 若是普遍位置求解部分已经是O(1)，不用再优化了
- 若是普遍位置求解部分是需要遍历的，则尝试使用斜率优化、临近位置观察法优化
设计暴力递归过程的原则：
1）每一个可变参数的类型，一定不要比int类型更加复杂
2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数 例如：贴纸问题
3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可
4）可变参数的个数，能少则少
# 题目一
较小集合的累加和问题，其实是个背包题
给定一个正数数组arr， 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近 返回： 最接近的情况下，较小集合的累加和
转化为arr的累加和sum, 求arr中子集合最接近sum/2
从左到右模型
暴力递归代码：
package class23;
/**
* - 给定一个正数数组arr，
* - 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
* - 返回：
* - 最接近的情况下，较小集合的累加和
* - 转化为arr的累加和sum, 求arr中子集合最接近sum/2
* @author yangyanchao
*
*/
public class Test01_SplitSumClosed {
public static int minSum(int[] arr) {
if(arr == null || arr.length == 0) {
return 0;
}
int sum = 0;
for(int value : arr) {
sum += value;
}
return process(arr, 0, sum / 2); // sum >> 1
}
/**
* - 求不超过rest下最大的(最接近)rest的集合累加和
* @param arr
* @param index
* @param rest
* @return
*/
private static int process(int[] arr, int index, int rest) {
if(index == arr.length) {
return 0;
}
// 不要
int p1 = process(arr, index + 1, rest);
// 要
int p2 = 0;
if(arr[index] <= rest) {
p2 = arr[index] + process(arr, index + 1, rest - arr[index]);
}
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
39
40
41
42
43
44
45
46
47
48
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
动态规划代码：
package class23;
/**
* - 给定一个正数数组arr，
* - 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
* - 返回：
* - 最接近的情况下，较小集合的累加和
* - 转化为arr的累加和sum, 求arr中子集合最接近sum/2
* @author yangyanchao
*
*/
public class Test01_SplitSumClosed {
public static int dp(int[] arr) {
if(arr == null || arr.length == 0) {
return 0;
}
int sum = 0;
for(int value : arr) {
sum += value;
}
sum /= 2;
int N = arr.length;
int[][] dp = new int[N + 1][sum + 1];
for(int index = N - 1; index >= 0; index--) {
for(int rest = 0; rest <= sum; rest++) {
// 不要
int p1 = dp[index + 1][rest];
// 要
int p2 = 0;
if(arr[index] <= rest) {
p2 = arr[index] + dp[index + 1][rest - arr[index]];
}
dp[index][rest] = Math.max(p1, p2);
}
}
return dp[0][sum];
}
}
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
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
# 题目二
较小集合的累加和问题，而且集合长度有限制个数
给定一个正数数组arr，请把arr中所有的数分成两个集合 如果arr长度为偶数，两个集合包含数的个数要一样多 如果arr长度为奇数，两个集合包含数的个数必须只差一个 请尽量让两个集合的累加和接近 返回： 最接近的情况下，较小集合的累加和
从左到右模型
字节跳动原题
暴力递归代码：
package class23;
/**
* - 给定一个正数数组arr，请把arr中所有的数分成两个集合
* - 如果arr长度为偶数，两个集合包含数的个数要一样多
* - 如果arr长度为奇数，两个集合包含数的个数必须只差一个
* - 请尽量让两个集合的累加和接近
* - 返回：
* - 最接近的情况下，较小集合的累加和
* - 这个转化为为arr的累加和sum, 求arr中子集合最接近sum/2 加上个数限制picks
* @author yangyanchao
*
*/
public class Test02_SplitSumClosedSizeHalf {
public static int minSumLimit(int[] arr) {
if(arr == null || arr.length == 0) {
return 0;
}
int sum = 0;
for(int value : arr) {
sum += value;
}
sum /= 2;
int N = arr.length;
if((N & 1) != 0) {
// 奇数
return Math.max(process(arr, 0, sum, (N - 1) >> 1), process(arr, 0, sum, ((N - 1) >> 1) + 1));
} else {
// 偶数
return process(arr, 0, sum, N >> 1);
}
}
/**
* - 返回不超过rest下，并且个数限制为limit的最大(最接近)rest的较小集合的累加和
* @param arr
* @param index
* @param rest
* @param limit
* @return
*/
private static int process(int[] arr, int index, int rest, int limit) {
if(index == arr.length) {
return limit == 0 ? 0 : -1;
}
// 不要
int p1 = process(arr, index + 1, rest, limit);
// 要
int p2 = -1;
int next = -1;
if(rest - arr[index] >= 0){
next = process(arr, index + 1, rest - arr[index], limit - 1);
if(next != -1) {
p2 = arr[index] + next;
}
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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
57
58
59
60
动态规划代码：
package class23;
/**
* - 给定一个正数数组arr，请把arr中所有的数分成两个集合
* - 如果arr长度为偶数，两个集合包含数的个数要一样多
* - 如果arr长度为奇数，两个集合包含数的个数必须只差一个
* - 请尽量让两个集合的累加和接近
* - 返回：
* - 最接近的情况下，较小集合的累加和
* - 这个转化为为arr的累加和sum, 求arr中子集合最接近sum/2 加上个数限制picks
* @author yangyanchao
*
*/
public class Test02_SplitSumClosedSizeHalf {
public static int dp1(int[] arr) {
if(arr == null || arr.length == 0) {
return 0;
}
int sum = 0;
for(int value : arr) {
sum += value;
}
sum /= 2;
int N = arr.length;
int[][][] dp = new int[N + 1][N + 1][sum + 1];
for(int rest = 0; rest <= sum; rest++) {
dp[N][0][rest] = 0;
for(int limit = 1; limit <= N; limit++) {
dp[N][limit][rest] = -1;
for(int index = N - 1; index >= 0; index--) {
// 不要
int p1 = dp[index + 1][limit][rest];
// 要
int p2 = -1;
int next = -1;
if(rest - arr[index] >= 0) {
next = dp[index + 1][limit - 1][rest - arr[index]];
if(next != -1) {
p2 = arr[index] + next;
}
}
dp[index][limit][rest] = Math.max(p1, p2);
}
}
}
if((N & 1) != 0) {
// 奇数
return Math.max(dp[0][(N - 1) >> 1][sum], dp[0][((N - 1) >> 1) + 1][sum]);
} else {
// 偶数
return dp[0][N >> 1][sum];
}
}
}
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
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
# 题目三
N皇后问题
N皇后问题是指在N*N的棋盘上要摆N个皇后， 要求任何两个皇后不同行、不同列， 也不在同一条斜线上 给定一个整数n，返回n皇后的摆法有多少种。
n=1，返回1 n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0 n=8，返回92
从左到右模型
不能转化为动态规划
N皇后问题只能暴力递归所以常常用于测试计算机的运算性能的
时间复杂度为O(n^n)
暴力递归代码：
思路：
- 一行摆一个皇后，所以按照行数
int row的递增来考虑- 要有个一维数组
int[] record记录之前行摆放了哪些皇后- 在该
row行下遍历列数int col- 验证
row行与col列在record记录下还能摆放的位置
package class23;
/**
* -
* - N皇后问题是指在N*N的棋盘上要摆N个皇后，
* - 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
* - 给定一个整数n，返回n皇后的摆法有多少种。
* - n=1，返回1
* - n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
* - n=8，返回92
* - 不能转化为动态规划
* - N皇后问题只能暴力递归所以常常用于测试计算机的运算性能的
* - 时间复杂度为O(n^n)
* @author yangyanchao
*
*/
public class Test03_NQueens {
public static int recordWays(int N) {
if(N < 1) {
return -1;
}
if(N == 1) {
return 1;
}
// 存放0-N-1行上皇后摆放的列
int[] record = new int[N];
return process(0, record, N);
}
/**
* - row 当前行判断该怎么摆放皇后
* @param row
* @param record
* @param n
* @return
*/
private static int process(int row, int[] record, int n) {
if(row == n) {
// 在不违反规则的前提下，row到了n行说明，0-n-1行已经摆好皇后了，所以返回1
return 1;
}
int ways = 0;
// row < n 0-n-1
for(int col = 0; col < n; col++) {
if(isCan(record, row, col)) {
record[row] = col;
ways += process(row + 1, record, n);
}
}
return ways;
}
/**
* - 判断record记录中 0-row-1行的位置有效性 record[x]=y 是指x行y列摆放了皇后
* - 如果record[x]==col || Math.abs(x-row) == Math.abs(y-col)
* @param record
* @param row
* @param col
* @return
*/
private static boolean isCan(int[] record, int row, int col) {
for(int i = 0; i < row; i++) {
if(record[i] == col || Math.abs(i - row) == Math.abs(record[i] - col)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int n = 7;
long start = System.currentTimeMillis();
System.out.println(recordWays(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
位运算代替record可以优化常数时间，但是只能到32皇后代码：
思路：
- 如果是7皇后问题，则准备一个限制数
limit(只获取为信息) -> 1<<N - 1- 准备列限制数
colLimit记录那些列已经不能选择了如：0000 0000 0100 0001，有1的位置代表不能选择了- 准备左下限制数
leftXiaLimit记录左下这个斜线上的位置已经不能选择了如：0000 0000 1000 0010，有1的位置代表不能选择了- 准备右下限制数
rightXiaLimit记录右下这个斜线上的位置已经不能选择了如：0000 0000 0010 0000，有1的位置代表不能选择了- 准备哪些位置可选的位运算数
pos = limit & (~(colLimit|leftXiaLimit|rightXiaLimit))列限制数与左下限制数与右下限制数相或再取反在与limit相与运算得出pos- 如果
pos不为0说明有位置可以选择，则提取最右侧的1int rightOne = pos & (~pos + 1)- 然后
post = post - rightOne，再试第二个右侧的1位置摆放皇后- 最后
colLimit = colLimit | rightOneleftXiaLimit = (leftXiaLimit | rightOne) << 1rightXiaLimit = (rightXiaLimit | rightOne) >> 1调用递归函数
对比分析：// N = 14 一维数组方法： 365596 4756ms 位运算方法： 365596 219ms1
2
3
4
5
6
7上面是一维数组实现的，下面是位运算实现N皇后
优化了常数时间
package class23;
/**
* -
* - N皇后问题是指在N*N的棋盘上要摆N个皇后，
* - 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
* - 给定一个整数n，返回n皇后的摆法有多少种。
* - n=1，返回1
* - n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
* - n=8，返回92
* - 不能转化为动态规划
* - N皇后问题只能暴力递归所以常常用于测试计算机的运算性能的
* - 时间复杂度为O(n^n)
* @author yangyanchao
*
*/
public class Test03_NQueens {
/**
* - 使用一维数组作为record记录实现N皇后问题
* @param N
* @return
*/
public static int recordWays(int N) {
if(N < 1) {
return -1;
}
if(N == 1) {
return 1;
}
// 存放0-N-1行上皇后摆放的列
int[] record = new int[N];
return process(0, record, N);
}
/**
* - row 当前行判断该怎么摆放皇后
* @param row
* @param record
* @param n
* @return
*/
private static int process(int row, int[] record, int n) {
if(row == n) {
// 在不违反规则的前提下，row到了n行说明，0-n-1行已经摆好皇后了，所以返回1
return 1;
}
int ways = 0;
// row < n 0-n-1
for(int col = 0; col < n; col++) {
if(isCan(record, row, col)) {
record[row] = col;
ways += process(row + 1, record, n);
}
}
return ways;
}
/**
* - 判断record记录中 0-row-1行的位置有效性 record[x]=y 是指x行y列摆放了皇后
* - 如果record[x]==col || Math.abs(x-row) == Math.abs(y-col)
* @param record
* @param row
* @param col
* @return
*/
private static boolean isCan(int[] record, int row, int col) {
for(int i = 0; i < row; i++) {
if(record[i] == col || Math.abs(i - row) == Math.abs(record[i] - col)) {
return false;
}
}
return true;
}
/**
* - 使用位运算方式实现N皇后问题 -->> 很有意思
* - 优化了常数时间 但是只能算出 1-31皇后问题
* - 位运算代替record可以优化常数时间，但是只能到32皇后代码：
* - `思路：`
* - 如果是7皇后问题，则准备一个限制数`limit(只获取为信息) -> 1<<N - 1`
* - 准备列限制数`colLimit`记录那些列已经不能选择了如：`0000 0000 0100 0001`，有1的位置代表不能选择了
* - 准备左下限制数`leftXiaLimit`记录左下这个斜线上的位置已经不能选择了如：`0000 0000 1000 0010`，有1的位置代表不能选择了
* - 准备右下限制数`rightXiaLimit`记录右下这个斜线上的位置已经不能选择了如：`0000 0000 0010 0000`，有1的位置代表不能选择了
* - 准备哪些位置可选的位运算数`pos = limit & (~(colLimit|leftXiaLimit|rightXiaLimit))` 列限制数与左下限制数与右下限制数相或再取反在与`limit`相与运算得出`pos`
* - 如果`pos不为0`说明有位置可以选择，则提取最右侧的1`int rightOne = pos & (~pos + 1) `
* - 然后`post = post - rightOne `，再试第二个右侧的1位置摆放皇后
* - 最后`colLimit = colLimit | rightOne` `leftXiaLimit = (leftXiaLimit | rightOne) << 1 ` `rightXiaLimit = (rightXiaLimit | rightOne) >> 1 `调用递归函数
* @param N
* @return
*/
public static int bitWays(int N) {
if(N < 1 || N > 32) {
return -1;
}
if(N == 1) {
return 1;
}
int limit = N == 32 ? -1 : (1 << N) - 1;
return process(limit, 0, 0, 0);
}
/**
* - 位运算实现N皇后递归函数
* @param limit 总限制数 一般用它做与运算来进行位运算的
* @param colLimit 列限制数
* @param leftXiaLimit 左下限制数
* @param rightXiaLimit 右下限制数
* @return
*/
private static int process(int limit, int colLimit, int leftXiaLimit, int rightXiaLimit) {
if(limit == colLimit) {
// 列限制数 与限制数相等了 因为每一行只选一个皇后，所以说明每一行上都已经选择了皇后
return 1;
}
// pos 存储的1代表，哪些位置还可以选择
int pos = limit & (~(colLimit | leftXiaLimit | rightXiaLimit));
int ans = 0;
while(pos != 0) {
int rightOne = pos & (~pos + 1);
pos = pos - rightOne;
ans += process(limit, colLimit | rightOne, (leftXiaLimit | rightOne) << 1, (rightXiaLimit | rightOne) >> 1);
}
return ans;
}
public static void main(String[] args) {
int n = 14;
long start = System.currentTimeMillis();
System.out.println(recordWays(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(bitWays(n));
end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141