Simple C++ DP solution sharing.


  • 0
    class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            int size = nums.size();
            vector<vector<int>> dp(size, vector<int>(size, -1));
            std::function<int(int, int)> compute = [&] (int a, int b) {
                if (a > b) return 0;
                if (dp[a][b] != -1) return dp[a][b];
                dp[a][b] = std::max(nums[a] + std::min(compute(a + 2, b),
                                                       compute(a + 1, b - 1)),
                                    nums[b] + std::min(compute(a, b - 2),
                                                       compute(a + 1, b - 1)));
                return dp[a][b];
            };
            int p1 = compute(0, size - 1);
            int p2 = std::accumulate(nums.begin(), nums.end(), 0) - p1;
            if (p1 >= p2) return true;
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.