|
怎么尝试一件事？
1）有经验但是没有方法论？
2）怎么判断一个尝试就是最优尝试？
3）难道尝试这件事真的只能拼天赋？那我咋搞定我的面试？
4）动态规划是啥？好高端的样子哦…可是我不会啊！和尝试有什么关系？
最强的私货来了！-> 暴力递归到动态规划的套路！解决任何面试中的动态规划问题！
?什么暴力递归可以继续优化？
有重复调用同一个子问题的解，这种递归可以优化
如果每一个子问题都是不同的解，无法优化也不用优化
?暴力递归和动态规划的关系
某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
但不是所有的暴力递归，都一定对应着动态规划
?面试题和动态规划的关系
解决一个问题，可能有很多尝试方法
可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式
一个问题?? 可能有?? 若干种动态规划的解法
?如何找到某个问题的动态规划方式？
1）设计暴力递归：重要原则+4种常见尝试模型！重点！
2）分析有没有重复解：套路解决
3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
4）看看能否继续优化：套路解决
?面试中设计暴力递归过程的原则
1）每一个可变参数的类型，一定不要比int类型更加复杂
2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数
3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可
4）可变参数的个数，能少则少
?知道了面试中设计暴力递归过程的原则，然后呢？
一定要逼自己找到不违反原则情况下的暴力尝试！
如果你找到的暴力尝试，不符合原则，马上舍弃！找新的！
如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%！
?常见的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，返回方法数。
暴力递归：?
public static int ways1(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
return process1(start, K, aim, N);
}
// 机器人当前来到的位置是cur，
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
// 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
public static int process1(int cur, int rest, int aim, int N) {
if (rest == 0) { // 如果已经不需要走了，走完了！
return cur == aim ? 1 : 0;
}
// (cur, rest)
if (cur == 1) { // 1 -> 2
return process1(2, rest - 1, aim, N);
}
// (cur, rest)
if (cur == N) { // N-1 <- N
return process1(N - 1, rest - 1, aim, N);
}
// (cur, rest)
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) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = -1;
}
}
// dp就是缓存表
// dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
// dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
// N+1 * K+1
return process2(start, K, aim, N, dp);
}
// cur 范: 1 ~ N
// rest 范：0 ~ K
public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
if (dp[cur][rest] != -1) {
return dp[cur][rest];
}
// 之前没算过！
int ans = 0;
if (rest == 0) {
ans = cur == aim ? 1 : 0;
} else if (cur == 1) {
ans = process2(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process2(N - 1, rest - 1, aim, N, dp);
} else {
ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
?改动态规划
public static int ways3(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
dp[aim][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[start][K];
}
?题目二
给定一个整型数组arr，代表数值不同的纸牌排成一条线
玩家A和玩家B依次拿走每张纸牌
规定玩家A先拿，玩家B后拿
但是每个玩家每次只能拿走最左或最右的纸牌
玩家A和玩家B都绝顶聪明
请返回最后获胜者的分数。
暴力递归
// 根据规则，返回获胜者的分数
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int first = f1(arr, 0, arr.length - 1);
int second = g1(arr, 0, arr.length - 1);
return Math.max(first, second);
}
// arr[L..R]，先手获得的最好分数返回
public 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);
}
// // arr[L..R]，后手获得的最好分数返回
public static int g1(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
return Math.min(p1, p2);
}
?添加缓存：
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
fmap[i][j] = -1;
gmap[i][j] = -1;
}
}
int first = f2(arr, 0, arr.length - 1, fmap, gmap);
int second = g2(arr, 0, arr.length - 1, fmap, gmap);
return Math.max(first, second);
}
// arr[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];
}
int ans = 0;
if (L == R) {
ans = arr[L];
} else {
int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
ans = Math.max(p1, p2);
}
fmap[L][R] = ans;
return ans;
}
// // arr[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];
}
int ans = 0;
if (L != R) {
int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
ans = Math.min(p1, p2);
}
gmap[L][R] = ans;
return ans;
}
动态规划
public static int win3(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
for (int i = 0; i < N; i++) {
fmap[i][i] = arr[i];
}
for (int startCol = 1; startCol < N; startCol++) {
int L = 0;
int R = startCol;
while (R < N) {
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++;
}
}
return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
}
|