<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>

class Solution {
public:
/*OPTIMAL GAME STRATEGY CONCEPT:
when its your turn do your best 
when its others turn expect least from him */

// RECURSION 2 : storing the difference of p1 and whatever the p2 returns and if this difference is >=0 p1 wins
#define ll long long int
/*ll  f(int s,int e,vector<int>& nums,vector<vector<ll>>&dp){
  if(s>e) return 0;// exhausted the nums
  if(s==e) return nums[s];// onle one ele left

if(dp[s][e]!=-1) return dp[s][e];

     ll take_s=0,take_e=0;
     take_s=nums[s] - f(s+1,e,nums,dp);
     take_e=nums[e] - f(s,e-1,nums,dp);

  return dp[s][e]=max(take_s,take_e);
} */
    bool predictTheWinner(vector<int>& nums) {
         int n=nums.size();
        
        //  vector<vector<ll>>dp(n+1,vector<ll>(n+1,-1));
        //  return f(0,n-1,nums,dp) >=0;
         //tabulation/Bottom up
         vector<vector<ll>>dp(n+2,vector<ll>(n+2,0));
         for(int s=n;s>=1;s--){
            for(int e=1;e<=n;e++){
                if(s==e) {
                    dp[s][e]=nums[s-1];
                    continue;
                }
                ll take_s=0,take_e=0;
                take_s=nums[s-1] - dp[s+1][e];
                take_e=nums[e-1] - dp[s][e-1];
                 dp[s][e]=max(take_s,take_e);
            }
         }
         return dp[1][n]>=0;  
    }
};
9600