【算法】【递归与动态规划模块】纸牌博弈问题（多线路型递归）

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定数组arr，现在有两个人A和B，分别从arr的头或者尾轮流取数字，并各自将取到的数组进行累加，直到arr数组被取完为止，A和B的数字累加和大的一方为胜出方，求胜出方获得的分数。

解决方案

原问题：
递归方法：
1、首先设计两个递归函数，分别为first和second，first函数入参：arr、left、right，代表arr[left…right]数组在先选的情况下获胜者的分数是多少。second函数入参：arr、left、right，代表arr[left…right]在后选择的情况下获胜者的分数是多少。
2、first表示先选，那么可以选择任何一边，选完之后自己就变成了第二个选择的人了，自己想要获胜就要返回 arr[left+1…right]和arr[left…right-1] 在第二个选择的情况下的最大值。
3、second表示第二个选，那么当前就变成第一个选了，也就是arr[left+1…right]和arr[left…right-1] 在第一个选择情况下的最大值。
详情见代码
动态规划：
通过递归可以提取出两个dp，分别代表第一个选择情况下获胜的分数和第二个选择下获胜的分数。
详情见代码

代码编写

java语言版本

原问题：
经典递归版本：

    /**
     * 二轮测试：递归方法
     * @param arr
     * @return
     */
    public static int winCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 对a来说是先走，对b来说是后走,取最大的
        return Math.max(first(arr, 0, arr.length-1), second(arr, 0, arr.length - 1)) ;
    }

    /**
     * 先选的人最终获得的分数
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int first(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        return Math.max(arr[left] + second(arr, left+1, right), arr[right] + second(arr, left, right-1));
    }

    /**
     * 后选的人最终获得的分数
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int second(int[] arr, int left, int right) {
        if (left == right) {
            // 第二个选就么得选
            return 0;
        }
        return Math.min(first(arr, left+1, right), first(arr, left, right-1));
    }
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

经典动态规划版本：

    /**
     * 二轮测试：动态规划方法
     * @param arr
     * @return
     */
    public static int dpCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 先选dp
        int[][] firstDp = new int[arr.length][arr.length];
        // 后选dp
        int[][] secondDp = new int[arr.length][arr.length];
        // 初始化
        for (int i = 0; i < arr.length; i++) {
            firstDp[i][i] = arr[i];
            secondDp[i][i] = 0;
        }
        for (int j = 1; j < arr.length; j++) {
            for (int i = j-1; i >= 0; i--) {
                firstDp[i][j] = Math.max(arr[i] + secondDp[i+1][j], arr[j] + secondDp[i][j-1]);
                secondDp[i][j] = Math.min(firstDp[i+1][j], firstDp[i][j-1]);
            }
        }
        return Math.max(firstDp[0][arr.length-1], secondDp[0][arr.length-1]);
    }
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

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

参考：https://swzhao.blog.csdn.net/article/details/127854150

这道题和“参考”这道题有一点点的相似之处，毕竟两道题都是两个dp并且dp的填充方式都差不多，所以我就比较好奇这是一种什么题型，首先我们把这道题两个递归的方式合并为一个递归的方式可以吗？肯定是可以的。只不过多一个参数代表 “第几个选”，然后根据参数进行判断，由此将两个递归可以合并成一个递归，如果你真的动手合并了一下那么应该也会觉得“参考”的递归代码结构体和这道题的非常相似，但是参考代码结构的那个是目标值aim，这里的是第一个选还是第二个选。我们发现这个入参可以将我们的递归分为两种不同的路线走下去，并不是传统的递归只有一条状态之间的递归线，前面我们做的题目都是传统的当前状态依赖前面的状态这种单一路线型逻辑，这句话不知道合不合适，我就命名为单一路线型递归问题。而参考题型和当前题型都算是多路线型递归，也就是说当前状态不完全的依赖前面的所有状态，而是会根据 一个标志性判断走不通的路线。这种题型需要在设计递归的时候增加这个标志而这个标志也是最难设计的，不过这个标志有一个特点，那就是范围绝对不会太大。比如aim只有两个状态true和false，当前题目只有两个状态：第一个选、第二个选。

这里拓展一下，如果三个人玩这个游戏呢？四个人呢？n个人呢？
如果你看懂了上面的解释，那么拓展多少人都可以，只不过那个标志性判断的范围就是 第一个选、第二个选、第三个选、第n个选。。。。

同时参考题目也可以变成 目标为 aim1的组合、目标为aim2的组合、目标为aim3的组合。。。千篇一律~

如果有朋友知道这种题型的专业术语请及时纠正哈~

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！