486. 预测赢家

题目:https://leetcode-cn.com/problems/predict-the-winner/

代码:

class Solution {

    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        //偶数长度下先手玩家必赢
        if (length % 2 == 0) {
            return true;
        }
        //进行动态规划求解
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i+1; j < length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] >= 0;
    }

}

第一次做动态规划的题目,没解出来。上述代码是看了题解之后写出来的。

首先题目意思是给出一个数组,两个玩家轮流选取数字,选中什么数字就给自己加多少分,只能从开头或者结尾选,直到数组被选完。最后看谁分数大谁就赢。问在每个玩家都很聪明的情况下,玩家1先手能否必赢。

理解了题目意思之后看代码,上述代码中有2大部分:

一、数组个数为偶数:

这种情况下如不考虑求分数的话,则不需要去计算。先手玩家必赢,原因是什么呢?且看如下分析:

假设数组的值为:[1, 5, 233, 7],那么每个数字的下标为:[0, 1, 2, 3],刚好2个偶数下标和2个奇数下标。假设先手玩家选取了开头即0下标数字,后手玩家能选取的只能是1下标或者3下标,发现了吗,是奇数下标,没有其他选择。这个时候无论后手玩家选择了哪个数,再次轮到先手玩家的时候,先手玩家一定可以再次选择偶数下标的位置。以此类推,我们可以发现,只要先手玩家愿意,先手玩家可以在整场游戏中只选取偶数下标的数字,同理也可以只选取奇数下标,这取决于先手玩家是第一次选择是先选开头还是结尾。

有了上述的条件,我们可以通过下标的奇偶性把数组分成2部分并计算他们的分值:偶数下标T1:1+233=234,奇数下标T2:5+7=13。又因为T1+T2=total(所有数字的总分),这个时候我们可以发现,T1和T2之间只有3种情况,T1>T2,T1=T2,T1<T2。因为题目规定,如果最后分值相等,也算玩家1获胜,所以玩家1先手只需要在游戏开始之时,计算出T1和T2的值,根据T1和T2哪个值大来决定都选偶数下标的数字还是奇数下标的数字即可。综上所述,在偶数个数的情况下,先手玩家必赢,压根无需计算。

二、数组个数为奇数:

这种情况下,只能中规中矩的去分析和计算解答。

如图,我们定义一个二维数组dp,行列都为数组的长度。这个时候我们需要理解表格中每个格子中数字的含义,即dp[i][j]中值代表这什么:

dp[i][j]的值代表,在i-j这个范围内的数字,我(先手)和对手经过各自的最优选择之后,我能领先的分数。注意这里的先手不考虑全局的范围,就考虑在i-j的范围内。也可以理解为,把原先的大数组,拆成多个i-j的小数组,每个小数组的情况都去计算结果,提前将结果缓存下来,避免使用递归方法调用时带来的重复计算。

了解了dp[i][j]值的含义之后,我们需要知道值的计算方法。

当i=j的时候,即只有一个数的情况下,那么先手玩家只能选择这个数,后手玩家没得选。所以dp[i][j]=dp[i][i]=nums[i],由此我们可以计算出表格中对角线的部分。

不考虑i>j的情况,所以表格中对角线下方即左下角的部分值不计算,即为默认的0,且没有任何作用。

当i<j的时候,先手玩家只有两种选择,选择nums[i]或者nums[j],当选择nums[i]时,先手玩家可以领先分数为(当前选择的分数减去剩下的数组中最优解下能领先的分数):nums[i]-dp[i+1][j],当选择nums[j]时,先手玩家可以领先分数为:nums[j]-dp[i][j-1]。此时先手玩家选择i还是j位置的数字取决于上述计算的2个分数哪个大,所以可以得出dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])。这个公式比较难理解,也是重点所在,可以多理解一会。

因为公式中的计算,会使用到dp的值,仔细看的话你会发现有点类似于递归函数。所以我们在计算整个dp表格的值的时候,按照图中箭头所示的顺序去计算。

综上,我们最终表格右上角即dp[0][length-1]的值如果大于等于0就代表着先手玩家1必赢。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏