LeetCode-486 预测赢家

题目描述

给定一个非负整数数组，两个玩家从任意两端拿取分数，最终分数最多的玩家获胜。

两个人都会使用使得自己分数最大的拿取方式，相同时先手获胜。

问先手是否会获胜。

思路

先从小情况进行考虑，设数组长度为 n，数组为[a, b, c, d, …]

使用{a, b, c, d, …}表示当前能够获得的最大分数。

因为先手后手都是要获得自己的最大分数，这样统一的定义对两者都成立。在拿取时，可以直接认为每次拿到的其实就是当前回合减去之前能够拿到的最大分数的最大值。

n=1，先手的最大分数为{a} = a；

n=2，先手的最大分数为{a, b} = max(a - {b}, b - {a})；

n=3，先手的最大分数为{a, b, c} = max(a - {b, c}, c - {a, b})；

n=4，同理为{a, b, c, d} = max(a - {b, c, d}, d - {a, b, c})。

……

这样只需要看最后能够获得的分数是否为一个非0值，即先手的收益是否为非负。

解这样一个问题，可以使用动态规划的思想，不断由小子集状态推出大子集的状态。每一个大小为L的子集都是由L-1的情况获得的，再加上起点位置的信息，即可求出结果。

时间复杂度为$ O(n^2) $， 空间复杂度$ O(n^2) $

（这种当前状态只由上一个状态得到的方案空间复杂度$O(n)$也是ok的）

代码

#include <bits/stdc++.h>
#include <vector>
using namespace std;
class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            int dp[20][20] = {0};
            int n = nums.size();

            for(int l = 0; l < n; l++) { // length
                for(int i = 0; i < n-l; i++) {    // start
                    if (l == 0) dp[l][i] = nums[i];
                    else {
                        dp[l][i]=max(nums[i]-dp[l-1][i+1], nums[i+l]-dp[l-1][i]);
                    }

                }
            }
            if(dp[n-1][0] >= 0) return true;
            else return false;

        }
};

int main() {
    Solution s;
    vector<int> v {1, 4, 1, 5, 2};
    cout << s.PredictTheWinner(v) << endl;;
}