<p>Alice and Bob take turns playing a game, with <strong>Alice starting first</strong>.</p>

<p>There are <code>n</code> stones arranged in a row. On each player&#39;s turn, they can <strong>remove</strong> either the leftmost stone or the rightmost stone from the row and receive points equal to the <strong>sum</strong> of the remaining stones&#39; values in the row. The winner is the one with the higher score when there are no stones left to remove.</p>

<p>Bob found that he will always lose this game (poor Bob, he always loses), so he decided to <strong>minimize the score&#39;s difference</strong>. Alice&#39;s goal is to <strong>maximize the difference</strong> in the score.</p>

<p>Given an array of integers <code>stones</code> where <code>stones[i]</code> represents the value of the <code>i<sup>th</sup></code> stone <strong>from the left</strong>, return <em>the <strong>difference</strong> in Alice and Bob&#39;s score if they both play <strong>optimally</strong>.</em></p>

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

<pre>
<strong>Input:</strong> stones = [5,3,1,4,2]
<strong>Output:</strong> 6
<strong>Explanation:</strong> 
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18 - 12 = 6.
</pre>

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

<pre>
<strong>Input:</strong> stones = [7,90,5,1,100,10,10,2]
<strong>Output:</strong> 122</pre>

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

<ul>
	<li><code>n == stones.length</code></li>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= stones[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:

        '''
        Alice first: max score diff.
        bob= minimize the score's difference
        
        Input: stones = [5,3,1,4,2]
        Alice:  5+3+1+4; 3+1+4+2

            removes 5: 3,1,4,2   ; 10
            removes2 2:  5,3,1,4 ; 13    V

        Bob:
            3,1,4,2 
                removes 3 : 1+4+2 = 7
                removes 2 : 3+1+4 = 8

             5,3,1,4
                removes 5 : 3+1+4 = 8
                removes 4 : 5+3+1 = 9     V

        Output: 6

        [5,3,1,4,2]
         ^      ^
         start  end


        //differentiate diff points


        '''


        sum_stones = 0
        for stone in stones:
            sum_stones += stone
      

        def points_at_step(isOdd, start_idx, end_idx, remaining_stones, dp):

            if (isOdd,start_idx,end_idx) in dp:
                return dp[(isOdd,start_idx,end_idx)]

            if start_idx > end_idx:
                return 0

            if isOdd: 
                points_end_move = points_at_step(not isOdd, start_idx, end_idx-1, remaining_stones-stones[end_idx], dp) + remaining_stones-stones[end_idx]          

                points_start_move = points_at_step(not isOdd, start_idx+1, end_idx, remaining_stones-stones[start_idx], dp) + remaining_stones-stones[start_idx]

                dp[(isOdd,start_idx,end_idx)] = max(points_end_move, points_start_move) 
                return dp[(isOdd,start_idx,end_idx)]

            else:
                points_end_move = points_at_step(not isOdd, start_idx, end_idx-1, remaining_stones-stones[end_idx], dp) - (remaining_stones-stones[end_idx] )         

                points_start_move = points_at_step(not isOdd, start_idx+1, end_idx, remaining_stones-stones[start_idx],dp) -(remaining_stones-stones[start_idx])


                dp[(isOdd,start_idx,end_idx)] = min(points_end_move, points_start_move)
                return dp[(isOdd, start_idx, end_idx)]

            
        dp = {}
        return points_at_step(True, 0, len(stones)-1, sum_stones, dp)
      


    # maximize the diff in a score
    # minimize the diff in a score

        
5042