486. Predict the Winner

https://leetcode.com/problems/predict-the-winner/description/
Solution 1. Recursion.
s1: score of player 1
s2: score of player 2
player 1's turn: t1 is true, player 1 wins if s1>=s2 for one of the two cases.
player 2's turn: t1 is false, player 1 wins if s1>=s2 for both of the two cases.
    bool PredictTheWinner(vector<int>& nums) {
        return predict(nums, 0, nums.size()-1, 0, 0, true);
    }
    bool predict(vector<int>& nums, int i, int j, int s1, int s2, bool t1) {
        if(i>j) {
            return s1>=s2;
        }
        if(t1) return predict(nums, i+1, j, s1+nums[i], s2, false)
            || predict(nums, i, j-1, s1+nums[j], s2, false);
        else return predict(nums, i+1, j, s1, s2+nums[i], true)
            && predict(nums, i, j-1, s1, s2+nums[j], true);
    }
Solution 2. Dynamic programming. 
dp[i][j] stores the score difference between player 1 and 2, when the numbers left are from index i to j, and player 1 is the next to play. See discussion session of LeetCode.
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int> (n));
        for(int i=0; i<n; i++) dp[i][i] = nums[i];
        for(int j=1; j<n; j++) {
            for(int i=j-1; i>=0; i--) {
                dp[i][j] = max(nums[j]-dp[i][j-1], nums[i]-dp[i+1][j]);
            }
        }
        return dp[0][n-1] >= 0;

    }