年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：玩家选数问题
实例2：
实例3：
实例4：
实例5：
实例1：玩家选数问题
有一排正数，玩家A和玩家B都可以看到。
每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。
玩家A先拿，玩家B再拿，两人交替拿走所有的数字，
两人都力争自己拿到的数的总和比对方多。请返回最后获胜者的分数。
例如：
5,2,3,4
玩家A先拿，当前他只能拿走5或者4。
如果玩家A拿走5，那么剩下2，3，4。轮到玩家B，此时玩家B可以选择2或4中的一个，…
如果玩家A拿走4，那么剩下5，2，3。轮到玩家B，此时玩家B可以选择5或3中的一个，…
思路1、递归: 暴力尝试
自己分别作为先选人，后选人，查看收益最大
无论是作为先选人，还是作为后选人，都是绝对理智的，每一次做出的选择都是最优的
具体过程见代码详解
1_1_递归过程依赖图.png
/**
* @description: 两人选数游戏
* 思路1、递归: 暴力尝试
* @version: 1.0
*/
public class Code_01_CardsInLine_1 {
// 方式1、递归: 暴力尝试
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) return 0;
// 自己分别作为先选人，后选人，查看收益最大
// 无论是作为先选人，还是作为后选人，都是绝对理智的，每一次做出的选择都是最优的
return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
}
/*
作为先选人，从 i 到 j 位置上获得的最大分数
核心：我作为先选人每一次决策都是选择的最优的
如：
5 2 3 4
那么我作为先选者一定最终做出的选择的是 （5 + 作为后选人最大分数）（4 + 作为后选人最大分数）中最大分数的
*/
public static int first(int[] arr, int i, int j) {
if (i == j) { // 只有一个数，同时作为先选人，当然返回这个唯一的数
return arr[i];
}
// 选择左边数，然后自己变成了后选人
// 从 i 到 j 位置上获得的最大分数 = 左边数 + 自己变为后选人从 i+1 到 j 位置上获得的最大分数
int L = arr[i] + second(arr, i + 1, j);
// 选择右边数，然后自己变成了后选人
// 从 i 到 j 位置上获得的最大分数 = 右边数 + 自己变为后选人从 i 到 j-1 位置上获得的最大分数
int R = arr[j] + second(arr, i, j - 1);
// 返回自己选择左边数和选择右边数两种情况下，最大的分数
return Math.max(L, R);
}
/*
作为后选人，从i 到 j 位置上获得的最大分数
核心：每一次都认为先选人做出的选择是最优的，留给自己的一定是最小的
5 2 3 4
先选人，选了 5 给自己留下 2 3 4 = 9
先选人，选了 4 给自己留下 5 2 3 = 10
先选人怎么可能那么好心让自己赢，我们都是绝对理智的人
所以
我作为后选人，悲催的只能在先选人选择后的区域选择我的数
但是我现在也不知道那边的数大，需要计算才能知道先选人选择的到底是哪边的数？
5 2 3 4
先选人，选了 5 给自己留下 2 3 4 = 9
先选人，选了 4 给自己留下 5 2 3 = 10
通过计算发现，9 < 10 ，先选人既然是绝对理智的，那么他给我留下的就是最小的
而我，只能从最小的那几个数中找最大的分数。
由于先选人已经选择了，现在他退位到后选人，我上了先选人位置，即，我现在是先选人。
总结: 我作为后选人做出什么样的决定，完全取决于先选人做出了什么决定，先选人扔给我的一定是最小的
*/
public static int second(int[] arr, int i, int j) {
if (i == j) { //只有一个数，自己作为后选人，自己前面有一个先选人，先选人选择后，剩下0个数可选
return 0;
}
// 现在我是先选人，选择左边数
int L = first(arr, i + 1, j);
// 现在我是先选人，选择右边数
int R = second(arr, i, j - 1);
// 我只能从最小的区域中进行选择
return Math.min(L, R);
}
}
思路2：从暴力递归到动态规划
暴力递归其实就是一个暴力尝试过程，尝试每一种选择
缺点：重复的大量计算，而且这种重复计算随着样本量的增加而指数式增加，做了很多无用功
暴力递归到动态规划的一般步骤
动态规划：
1、写出暴力尝试
2、确定最终解，是什么点
3、查看暴力尝试过程中的计算解，是否是完全无后效性的
4、找到可以代替解的变量
5、base case 给表赋值
6、一般情况的依赖关系
根据题具体分析
1、暴力尝试：win1()
2、确定最终解：(0, N-1) 点
3、win1() 中 f(arr, i, j) arr 是固定值，f(i , j) 是无效性的
4、可以用 i , j 表示解
5、根据递归中的base case 来给表赋值（不变值，基本情况下的值，如本题 i==j 时）
6、一般情况下的依赖关系
first() (i,j) 依赖于second() 中的 (i+1, j) 和 (i, j-1)
second() (i,j) 依赖于 first() 中的 (i+1,j) 和 (i, j-1)
1_2_fs依赖关系.png
import static cn.zqtao.learn.nowcode_other.day1.Code_01_CardsInLine_1.win1;
/**
* @description: 两人选数游戏
* 思路2：从暴力递归到动态规划
* <p>
* 暴力递归其实就是一个暴力尝试过程，尝试每一种选择
* 缺点：重复的大量计算，而且这种重复计算随着样本量的增加而指数式增加，做了很多无用功
* <p>
* 动态规划：
* 1、写出暴力尝试
* 2、确定最终解，是什么点
* 3、查看暴力尝试过程中的计算解，是否是完全无后效性的
* 4、找到可以代替解的变量
* 5、base case 给表赋值
* 6、一般情况的依赖关系
* <p>
* 1、暴力尝试：win1()
* 2、确定最终解：(0, N-1) 点
* 3、win1() 中 f(arr, i, j) arr 是固定值，f(i , j) 是无效性的
* 4、可以用 i , j 表示解
* 5、根据递归中的base case 来给表赋值（不变值，基本情况下的值，如本题 i==j 时）
* 6、一般情况下的依赖关系
* first() (i,j) 依赖于second() 中的 (i+1, j) 和 (i, j-1)
* second() (i,j) 依赖于 first() 中的 (i+1,j) 和 (i, j-1)
* <p>
* <p>
* 暴力尝试可以使用表进行表示
* dpf 可以保存所有 first() 的所有情况
* dps 可以保存所有 second() 的所有情况
* <p>
* first() 中
* @version: 1.0
*/
public class Code_02_CardsInLine_2 {
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) return 0;
// 保存各种状态
int[][] dpf = new int[arr.length][arr.length];
int[][] dps = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
dpf[j][j] = arr[j]; // first() 中 base case 中 i==j 情况赋值
// dps[j][j] = 0; // second() 中 base case 中 i==j 情况，由于Java是自动给数组初始化为0 的所以可以忽略
for (int i = j - 1; i >= 0; i--) {
// 一般情况依赖关系
// first() (i,j) 依赖于second() 中的 (i+1, j) 和 (i, j-1)
dpf[i][j] = Math.max(arr[i] + dps[i + 1][j], arr[j] + dps[i][j - 1]);
// second() (i,j) 依赖于 first() 中的 (i+1,j) 和 (i, j-1)
dps[i][j] = Math.min(dpf[i + 1][j], dpf[i][j - 1]);
}
}
return Math.max(dpf[0][arr.length - 1], dps[0][arr.length - 1]);
}
public static int[] generateRandomArr(int maxSize, int maxValue) {
int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
return arr;
}
public static void main(String[] args) {
int maxSize = 5;
int testTime = 50000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArr(maxSize, 20);
int r1 = win1(arr);
int r2 = win2(arr);
if (r1 != r2) {
System.out.println("error");
}
}
}
}
网友评论