Leetcode:486. Predict the Winner

Posted on | Comments: | Views:
DP

486. Predict the Winner

题目理解:

有两个玩家, 每个玩家每次可以选择数组头或为的数作为得分, 交替进行, 玩家1先选. 假如两个玩家都以最优策略进行游戏, 对于给出的数组, 判断玩家1是否能取胜.

思路:

用 f[i][j][p] 记录得分, 表示对于数组[i, j]段先手取p的最大得分(p=0, 头, p=1, 尾);
所以问题的答案就是 f[0][n-1] 的两个值是否大于对应后手两个值的真假关系


要写出 f[0][n-1] 状态转移方程要考虑的问题: 假如先取数组头, 那么就要求 f[0][n-1][0], 这时候剩下 [1, n-1], 因为玩家总是进行最优取法, 所以后取的会选 f[1][n-1][0] 和 f[1][n-1][1] 中较大值, 根据这个选择, f[0][n-1][0] 只能取到剩下的部分, [2, n-1] 或 [1, n-2]; f[0][n-1][1] 也是如此, 这样就能够写出状态转移方程了. 

1
2
f[x][y][0] = nums[x] + (f[x+1][y][0]>f[x+1][y][1]?max(f[x+2][y][0], f[x+2][y][1]):max(f[x+1][y-1][0], f[x+1][y-1][1]));
f[x][y][1] = nums[y] + (f[x][y-1][0]>f[x][y-1][1]?max(f[x+1][y-1][0], f[x+1][y-1][1]):max(f[x][y-2][0], f[x][y-2][1]));


实现的时候用了递归的方法, 编程难度较低; 初始状态需要算每个 f[i][i][0] f[i][i][1];

小结:

这道题还有其他更好的做法, 给个方向, 对于[i, j], 一个人若是取了 g[i][j], 那么另一个人的得分肯定是 Total[i][j] - g[i][j], 状态转移: g[i][j] = max{ n(i) + Total[i+1][j] - g[i+1][j], n(j) + Total[i][j-1] - g[i][j-1] }

Submission Detail:

code:

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
48
49
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int n;
    int f[21][21][2];
    bool PredictTheWinner(vector<int>& nums) {
        n = nums.size();
        if (n == 1 || n == 2 || n == 0) {
            return true;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j][0] = -1;
                f[i][j][1] = -1;
            }
        }
        for (int i = 0; i < n; ++i) {
            f[i][i][0] = nums[i];
            f[i][i][1] = nums[i];
        }
        find(0, n-1, nums);

        return f[0][n-1][0] >= max(f[1][n-1][0], f[1][n-1][1]) || f[0][n-1][1] >= max(f[0][n-2][0], f[0][n-2][1]); 
    }
    void find(int x, int y, vector<int>& nums) {
        if (f[x][y][0] != -1 || y < x) {
            return;
        }
        if (y-x>=2) {
            find(x+1, y, nums);
            find(x, y-1, nums);
            find(x+1, y-1, nums);
            find(x+2, y, nums);
            find(x, y-2, nums);
            f[x][y][0] = nums[x] + (f[x+1][y][0]>f[x+1][y][1]?max(f[x+2][y][0], f[x+2][y][1]):max(f[x+1][y-1][0], f[x+1][y-1][1]));
            f[x][y][1] = nums[y] + (f[x][y-1][0]>f[x][y-1][1]?max(f[x+1][y-1][0], f[x+1][y-1][1]):max(f[x][y-2][0], f[x][y-2][1]));
        } else {
            f[x][y][0] = nums[x];
            f[x][y][1] = nums[y];
        }
    }
    int max(int x, int y) {
        return x>y?x:y;
    }
};