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

    using pii = pair<int, int>;
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<pii>> p1(n + 1, vector<pii>(n + 1, make_pair(0, 0)));
        vector<vector<pii>> p2(n + 1, vector<pii>(n + 1, make_pair(0, 0)));
        p1[n - 1][n] = make_pair(nums[n-1], 0);
        p2[n - 1][n] = make_pair(0, nums[n-1]);
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j <= n; ++j) {
                auto picksLeft = make_pair(nums[i] + p2[i + 1][j].first, p2[i + 1][j].second);
                auto picksRight = make_pair(nums[j - 1] + p2[i][j - 1].first, p2[i][j - 1].second);
                if (picksLeft.first >= picksRight.first) {
                    p1[i][j] = picksLeft;
                } else {
                    p1[i][j] = picksRight;
                }
                
                picksLeft = make_pair(p1[i + 1][j].first, nums[i] + p1[i + 1][j].second);
                picksRight = make_pair(p1[i][j - 1].first, nums[j - 1] + p1[i][j - 1].second);
                
                if (picksLeft.second >= picksRight.second) {
                    p2[i][j] = picksLeft;
                } else {
                    p2[i][j] = picksRight;
                }
            }
        }

        return p1[0][n].first >= p1[0][n].second;
    }

};
9700