486. Predict the Winner | 486. 预测赢家（博弈论）

本是古典何须时尚 2022-09-10 10:23 143阅读 0赞

## 题目 ##

[https://leetcode.com/problems/predict-the-winner/][https_leetcode.com_problems_predict-the-winner]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

这道题和 [leetcode 877. Stone Game | 877. 石子游戏（递归/动态规划/数学解法）][leetcode 877. Stone Game _ 877.] 比较像。一开始以为又是一个恒等问题，后来看了答案发现并不是。而且从数据规模上来看，这题用暴力是能通过的。

class Solution { 
        public boolean PredictTheWinner(int[] nums) { 
            if (nums.length % 2 == 0) return true; // 偶数个先手必胜
            else return getMaxScore(nums, 0, nums.length - 1) >= 0;
        }
    
        public int getMaxScore(int[] nums, int L, int R) {  // 计算作为当前轮的先手，能比对方多得的分数
            if (L == R) return nums[L];
            int left = nums[L] - getMaxScore(nums, L + 1, R); // 选左边
            int right = nums[R] - getMaxScore(nums, L, R - 1); // 选右边
            return Math.max(left, right);
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_predict-the-winner]: https://leetcode.com/problems/predict-the-winner/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a733f60468c64a54bf5021243a00f484.png
[leetcode 877. Stone Game _ 877.]: https://blog.csdn.net/sinat_42483341/article/details/119451305
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/f408f15959184a9bac1c33c876375505.png