recursive

class Solution {
public:
    bool PredictTheWinner(vector<int>& a) {
        const int n = (int)a.size();
        int sm = 0;
        for(int i = 0; i < n; i++) sm += a[i];
        int dp[n][n][2];
        memset(dp, -1, sizeof dp);
        function<int(int, int, int)> f = [&](int l, int r, int t) {
            if(l > r) return 0;
            int& ans = dp[l][r][t];
            if(ans != -1) return ans;
            if(t) ans = min(f(l + 1, r, 1 - t), f(l, r - 1, 1 - t));
            else ans = max(f(l + 1, r, 1 - t) + a[l], f(l, r - 1, 1 - t) + a[r]);
            return ans;
        };
        int res = f(0, n - 1, 0);
        return res >= sm - res;
    }
};