leetcode-predict-winner

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/predict-the-winner/

　　给你一个数组，有两个player从数组中拿数，你现在是player1，也就是说先拿，判断最后你拿到的数字之和是否比player2多就赢了，具体拿数规则是只能从数组两端选择一个数拿走，拿走的数以后不能重复拿取。

题目分析

　　动态规划，跟之前的Can I Win有些类似之处，二维数组中f[i][j]含义是原数组的[i,j]闭区间上player1进行按规则选择所能得到的最大和，那么最后只要和能大于等于总和的一半就赢了。

代码

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
42
43
44
45
46
47
public class Solution {
    private int[][] f;
    private int[] nums;
    private int len;
    private int total;
    
    private int search(int s, int e) {
        if (s == e) {
            return nums[s];
        }
        if (s + 1 == e) {
            return Math.max(nums[s], nums[s + 1]);
        }
        if (f[s][e] >= 0) {
            return f[s][e];
        }
        // 先选s->[s + 1, e]
        int a = search(s + 2, e);
        int b = search(s + 1, e - 1);
        int max1 = Math.min(a, b) + nums[s]; // player2也要选取最优
        
        //尝试e->[s, e - 1]
        int c = search(s, e - 2);
        int d = b;
        int max2 = Math.min(c, d) + nums[e]; // player2也要选取最优
        return f[s][e] = Math.max(max1, max2);
    }
    
    public boolean PredictTheWinner(int[] nums) {
        this.nums = nums;
        len = nums.length;
        f = new int[len][len];
        for (int i = 0; i < len; i++) {
            Arrays.fill(f[i], -1);
        }
        for (int n : nums) {
            total += n;
        }
        int half = -1;
        if (total % 2 == 0) {
            half = total / 2;
        } else {
            half = (total + 1) / 2;
        }
        return search(0, len - 1) >= half;
    }
}

　　时间复杂度：O(n ^ 2)