# 第18节 暴力递归到动态规划（一）
# 怎么尝试一件事？
- 有经验但是没有方法论？
- 怎么判断一个尝试就是最优尝试？
- 难道尝试这件事真的只能拼天赋？那我咋搞定我的面试？
- 动态规划是啥？好高端的样子哦…可是我不会啊！和尝试有什么关系？
最强的私货来了！-> 暴力递归到动态规划的套路！解决任何面试中的动态规划问题！
# 什么暴力递归可以继续优化？
- 有重复调用同一个子问题的解，这种递归可以优化
- 如果每一个子问题都是不同的解，无法优化也不用优化
# 暴力递归和动态规划的关系
- 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
- 任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
- 但不是所有的暴力递归，都一定对应着动态规划
# 面试题和动态规划的关系
- 解决一个问题，可能有很多尝试方法
- 可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式
- 一个问题 可能有 若干种动态规划的解法
# 如何找到某个问题的动态规划方式？
- 设计暴力递归：重要原则+4种常见尝试模型！重点！
- 分析有没有重复解：套路解决
- 用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
- 看看能否继续优化：套路解决
# 面试中设计暴力递归过程的原则
- 每一个可变参数的类型，一定不要比int类型更加复杂
- 原则1可以违反，让类型突破到一维线性结构，那必须是单一可变参数
- 如果发现原则1被违反，但不违反原则2，只需要做到记忆化搜索即可
- 可变参数的个数，能少则少
# 知道了面试中设计暴力递归过程的原则，然后呢？
- 一定要逼自己找到不违反原则情况下的暴力尝试！
- 如果你找到的暴力尝试，不符合原则，马上舍弃！找新的！
- 如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%！
# 常见的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;
/**
* 机器人行进问题
* @author yangyanchao
*
*/
public class Test01_RobotWalk {
/**
* 机器人行进问题 返回方法数
* @param N 位置数
* @param M 机器人开始位置
* @param P 机器人最终去往的位置
* @param K 机器人走的步数
* @return
*/
public static int robotWalk1(int N, int M, int P, int K) {
if(N < 2 || M > N || M < 1 || P > N || P < 1 || K < 1) {
// 非法参数
return -1;
}
return process1(M, K, P, N);
}
/**
* 暴力递归过程
* @param cur 当前机器人来到的位置
* @param rest 机器人剩余步数
* @param end 最终来到的位置
* @param n 总位置数
* @return
*/
private static int process1(int cur, int rest, int end, int n) {
if(rest == 0) {
// 没有步数了 来到了最终位置则返回1否则返回0
return cur == end ? 1 : 0;
}
// rest != 0
if(cur == 1) {
// 如果机器人来到1位置，那么下一步只能往右来到2位置
return process1(2, rest - 1, end, n);
}
if(cur == n) {
// 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置
return process1(n - 1, rest - 1, end, n);
}
// 如果机器人来到中间位置，那么下一步可以往左走或者往右走
// 往左走
int ans = process1(cur - 1, rest - 1, end, n);
// 往右走
ans += process1(cur + 1, rest - 1, end, n);
return ans;
}
public static void main(String[] args) {
System.out.println(robotWalk1(5, 2, 4, 6));
}
}
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
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
记忆化搜索(傻缓存)代码：
package class18;
/**
* 机器人行进问题
* @author yangyanchao
*
*/
public class Test01_RobotWalk {
/**
* 机器人行进问题 返回方法数
* @param N 位置数
* @param M 机器人开始位置
* @param P 机器人最终去往的位置
* @param K 机器人走的步数
* @return
*/
public static int robotWalk2(int N, int M, int P, int K) {
if(N < 2 || M > N || M < 1 || P > N || P < 1 || K < 1) {
// 非法参数
return -1;
}
// 加入傻缓存
// 分析cur与rest取值范围
// cur 1...N
// rest 1...K
int[][] dp = new int[N + 1][K + 1];
// 初始化dp -1 一开始都没有算过
for(int i = 0; i <= N; i++) {
for(int j = 0; j <= K; j++) {
dp[i][j] = -1;
}
}
return process2(M, K, P, N, dp);
}
/**
* 暴力递归过程
* 加入傻缓存
* @param cur 当前机器人来到的位置
* @param rest 机器人剩余步数
* @param end 最终来到的位置
* @param n 总位置数
* @param dp 缓存
* @return
*/
private static int process2(int cur, int rest, int end, int n, int[][] dp) {
if(dp[cur][rest] != -1) {
return dp[cur][rest];
}
int ans = 0;
if(rest == 0) {
ans = cur == end ? 1 : 0;
} else if(cur == 1) {
ans = process2(2, rest - 1, end, n, dp);
} else if(cur == n) {
ans = process2(n - 1, rest - 1, end, n, dp);
} else {
ans = process2(cur - 1, rest - 1, end, n, dp) + process2(cur + 1, rest - 1, end, n, dp);
}
dp[cur][rest] = ans;
return ans;
}
public static void main(String[] args) {
System.out.println(robotWalk2(5, 2, 4, 6));
}
}
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
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
分析位置依赖：
假设：有5个位置：N=5，机器人开始来到2位置M=2，最终到4位置P=4，走了6步K=6
0行是无效的，0列的是
cur==4?1:0，1行的数据依赖左下的dp[2][rest-1]，5行的数据依赖左上的dp[n-1][rest-1]，普通位置依赖左上与左下的和如下表格做出位置依赖依次求出位置上的数就是动态规划：
0 1 2 3 4 5 6 0 -1 -1 -1 -1 -1 -1 -1 1 0 0 0 1 0 4 0 2 0 0 1 0 4 0 13 3 0 1 0 3 0 9 0 4 1 0 2 0 5 0 14 5 0 1 0 2 0 5 0 最终求
dp[2][6] == 13
动态规划代码：
package class18;
/**
* 机器人行进问题
* @author yangyanchao
*
*/
public class Test01_RobotWalk {
/**
* 机器人行进问题 返回方法数
* 动态规划
* @param N 位置数
* @param M 机器人开始位置
* @param P 机器人最终去往的位置
* @param K 机器人走的步数
* @return
*/
public static int robotWalk3(int N, int M, int P, int K) {
if(N < 2 || M > N || M < 1 || P > N || P < 1 || K < 1) {
// 非法参数
return -1;
}
int[][] dp = new int[N + 1][K + 1];
dp[P][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[M][K];
}
public static void main(String[] args) {
System.out.println(robotWalk3(5, 2, 4, 6));
}
}
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
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
# 题目二
纸牌问题
范围上的尝试模型给定一个整型数组arr，代表数值不同的纸牌排成一条线 玩家A和玩家B依次拿走每张纸牌 规定玩家A先拿，玩家B后拿 但是每个玩家每次只能拿走最左或最右的纸牌 玩家A和玩家B都绝顶聪明 请返回最后获胜者的分数。
分为先手与后手，拿走纸牌获得牌值分数，返回先手与后手情况下的最大分数
暴力递归代码：
package class18;
/**
* 纸牌问题
* @author yangyanchao
*
*/
public class Test02_CardsInLine {
/**
* 纸牌问题
* 暴力递归过程
* 分为先手与后手，拿走纸牌获得牌值分数，返回先手与后手情况下的最大分数
* @return
*/
public static int cardsInLine1(int[] arr) {
if(arr == null || arr.length == 0) {
return -1;
}
int first = f1(arr, 0, arr.length - 1);
int second = g1(arr, 0, arr.length - 1);
return Math.max(first, second);
}
/**
* 先手情况下的最大分数
* @param arr
* @param L
* @param R
* @return
*/
private 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);
}
/**
* 后手情况下的最大分数
* @param arr
* @param L
* @param R
* @return
*/
private static int g1(int[] arr, int L, int R) {
if(L == R) {
// 剩一张牌的时候 轮不上我选择
return 0;
}
// 牌不止一张
// 先手选择左边的 那我在剩下的牌中尽我最大的努力
int p1 = f1(arr, L + 1, R);
// 先手选择右边的 那我在剩下的牌中尽我最大的努力
int p2 = f1(arr, L, R - 1);
// 但是先手绝顶聪明不会让我得到这两种情况下的最大情况的 所以我只能得到最小分数情况
return Math.min(p1, p2);
}
public static void main(String[] args) {
int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
System.out.println(cardsInLine1(arr));
}
}
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
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
记忆化搜索(傻缓存)代码：
package class18;
/**
* 纸牌问题
* @author yangyanchao
*
*/
public class Test02_CardsInLine {
/**
* 纸牌问题
* 加入缓存
* 分为先手与后手，拿走纸牌获得牌值分数，返回先手与后手情况下的最大分数
* @return
*/
public static int cardsInLine2(int[] arr) {
if(arr == null || arr.length == 0) {
return -1;
}
int N = arr.length;
int[][] fdp = new int[N][N];
int[][] gdp = new int[N][N];
// 初始化为-1
for(int L = 0; L < N; L++) {
for(int R = 0; R < N; R++) {
fdp[L][R] = -1;
gdp[L][R] = -1;
}
}
int first = f2(arr, 0, N - 1, fdp, gdp);
int second = g2(arr, 0, N - 1, fdp, gdp);
return Math.max(first, second);
}
/**
* 先手情况下的最大分数
* @param arr
* @param L
* @param R
* @param fdp
* @param gdp
* @return
*/
private static int f2(int[] arr, int L, int R, int[][] fdp, int[][] gdp) {
if(fdp[L][R] != -1) {
return fdp[L][R];
}
if(L == R) {
fdp[L][R] = arr[L];
return arr[L];
}
// 牌不止一张
// 拿左边的牌
int p1 = arr[L] + g2(arr, L + 1, R, fdp, gdp);
// 拿右边的牌
int p2 = arr[R] + g2(arr, L, R - 1, fdp, gdp);
int ans = Math.max(p1, p2);
fdp[L][R] = ans;
return ans;
}
/**
* 后手情况下的最大分数
* @param arr
* @param L
* @param R
* @param fdp
* @param gdp
* @return
*/
private static int g2(int[] arr, int L, int R, int[][] fdp, int[][] gdp) {
if(gdp[L][R] != -1) {
return gdp[L][R];
}
if(L == R) {
// 剩一张牌的时候 轮不上我选择
fdp[L][R] = 0;
return 0;
}
// 牌不止一张
// 先手选择左边的 那我在剩下的牌中尽我最大的努力
int p1 = f2(arr, L + 1, R, fdp, gdp);
// 先手选择右边的 那我在剩下的牌中尽我最大的努力
int p2 = f2(arr, L, R - 1, fdp, gdp);
// 但是先手绝顶聪明不会让我得到这两种情况下的最大情况的 所以我只能得到最小分数情况
int ans = Math.min(p1, p2);
gdp[L][R] = ans;
return ans;
}
public static void main(String[] args) {
int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
System.out.println(cardsInLine2(arr));
}
}
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
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
分析位置依赖：
假设：
int[] arr = { 5, 7, 4, 5, 8 };
fdp
L==R -> arr[L]
fdp[L][R]->arr[L] + gdp[L+1][R]与arr[R] + gdp[L][R-1] 取最大值
0 1 2 3 4 0 5 7 9 11 17 1 -1 7 7 11 13 2 -1 -1 4 5 12 3 -1 -1 -1 5 8 4 -1 -1 -1 -1 8
gdp
L==R -> 0
gdp[L][R]->fdp[L+1][R]与fdp[L][R-1]取最小值
0 1 2 3 4 0 0 5 7 9 11 1 -1 0 4 5 11 2 -1 -1 0 4 5 3 -1 -1 -1 0 5 4 -1 -1 -1 -1 0 最后取
fdp[0][4]与gdp[0][4]最大值就是17
动态规划代码：
package class18;
/**
* 纸牌问题
* @author yangyanchao
*
*/
public class Test02_CardsInLine {
/**
* 纸牌问题
* 动态规划
* 分为先手与后手，拿走纸牌获得牌值分数，返回先手与后手情况下的最大分数
* @return
*/
public static int cardsInLine3(int[] arr) {
if(arr == null || arr.length == 0) {
return -1;
}
int N = arr.length;
int[][] fdp = new int[N][N];
int[][] gdp = new int[N][N];
for(int i = 0; i < N; i++) {
fdp[i][i] = arr[i];
gdp[i][i] = 0;
}
for(int R = 1; R < N; R++) {
int startL = 0;
int startR = R;
while(startR < N) {
fdp[startL][startR] = Math.max(arr[startL] + gdp[startL + 1][startR], arr[startR] + gdp[startL][startR - 1]);
gdp[startL][startR] = Math.min(fdp[startL + 1][startR], fdp[startL][startR - 1]);
startL++;
startR++;
}
}
return Math.max(fdp[0][N - 1], gdp[0][N - 1]);
}
public static void main(String[] args) {
int[] arr = { 5, 7, 4, 5, 8 };
System.out.println(cardsInLine3(arr));
}
}
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
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