<p>You are given an integer array <code>nums</code>. Two players are playing a game with this array: player 1 and player 2.</p>

<p>Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of <code>0</code>. At each turn, the player takes one of the numbers from either end of the array (i.e., <code>nums[0]</code> or <code>nums[nums.length - 1]</code>) which reduces the size of the array by <code>1</code>. The player adds the chosen number to their score. The game ends when there are no more elements in the array.</p>

<p>Return <code>true</code> if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return <code>true</code>. You may assume that both players are playing optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,233,7]
<strong>Output:</strong> true
<strong>Explanation:</strong> Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 20</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>
</ul>

// Recursion tarika 1
class Solution1 {
public:
    // Ye function player1 ka score nikalega, min-max game strategy leke,

    long long solve(vector<int>& nums, int i, int j, vector<vector<long long>>& mem) {
        if (i > j) return 0;

        // 1 ne i liya, phir 2 agar i+1 lega to solve(i+2, j) call hoga, aur agar j lega to
        // solve(i+1, j-1) (Next call) call hoga 

        // 1 ne j liya, phir 2 agar i lega to solve(i+1, j-1) call hoga, aur agar j-1 lega to
        // solve(i, j-2) (Next call) call hoga 

        if (mem[i][j] != -1) return mem[i][j];

        long long takeI = nums[i] + min(solve(nums, i+2, j, mem), solve(nums, i+1, j-1, mem));
        long long takeJ = nums[j] + min(solve(nums, i+1, j-1, mem), solve(nums, i, j-2, mem));
        
        return mem[i][j] = max(takeI, takeJ);
    }
    bool predictTheWinner(vector<int>& nums) {
        long long sum = 0;
        for (int num: nums) sum += num;

        int n = nums.size();
        vector<vector<long long>> mem(n+1, vector<long long>(n+1, -1));
        long long player1Score = solve(nums, 0, nums.size() -1, mem);
        long long player2Score = sum - player1Score;
        if (player1Score >= player2Score) return true;
        else return false;
    }
};



// Recursion tarika 2
class Solution {
public:
    // Ye function player1 aur player2 ka difference nikalega, min-max game strategy leke,
    // Yaha pe player1 ke score ko lete jayenge aur usme se player2 ka score minus karte jayenge

    long long solve(vector<int>& nums, int i, int j, vector<vector<long long>>& mem) {
        if (i > j) return 0;

        if (mem[i][j] != -1) return mem[i][j];

        // 1 ne agar i liya to uska score le liya phir 2 jo hai wo (i+1) ya j me kuch lega to uska score minus kar denge
        // Same for agar 1 ne j liya

        long long takeI = nums[i] - solve(nums, i+1, j, mem);
        long long takeJ = nums[j] - solve(nums, i, j-1, mem);
        
        return mem[i][j] = max(takeI, takeJ);
    }

    bool predictTheWinner(vector<int>& nums) {
    
        int n = nums.size();
        vector<vector<long long>> mem(n+1, vector<long long>(n+1, -1));
        return solve(nums, 0, nums.size() -1, mem) >=0;
    }
};
9500