Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 486. Predict the Winner

---

題目：


方法：

我的收益 = 目前拿到 - 對手最佳收益

解答：

class Solution {
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> visited(n, vector<int>(n, INT_MIN));

        auto dfs = [&](this auto&& dfs, int l , int r) {
            if (l == r) {
                return nums[l];
            }

            if (visited[l][r] != INT_MIN) {
                return visited[l][r];
            }

            int tl = nums[l] - dfs(l + 1, r);
            int tr = nums[r] - dfs(l, r - 1);
            return visited[l][r] = max(tl, tr);
        };

        return dfs(0, n - 1) >= 0;
    }
};