<p>There are several stones <strong>arranged in a row</strong>, and each stone has an associated value which is an integer given in the array <code>stoneValue</code>.</p>

<p>In each round of the game, Alice divides the row into <strong>two non-empty rows</strong> (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice&#39;s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.</p>

<p>The game ends when there is only <strong>one stone remaining</strong>. Alice&#39;s is initially <strong>zero</strong>.</p>

<p>Return <i>the maximum score that Alice can obtain</i>.</p>

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

<pre>
<strong>Input:</strong> stoneValue = [6,2,3,4,5,5]
<strong>Output:</strong> 18
<strong>Explanation:</strong> In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice&#39;s score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice&#39;s score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice&#39;s score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.
</pre>

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

<pre>
<strong>Input:</strong> stoneValue = [7,7,7,7,7,7,7]
<strong>Output:</strong> 28
</pre>

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

<pre>
<strong>Input:</strong> stoneValue = [4]
<strong>Output:</strong> 0
</pre>

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

<ul>
	<li><code>1 &lt;= stoneValue.length &lt;= 500</code></li>
	<li><code>1 &lt;= stoneValue[i] &lt;= 10<sup>6</sup></code></li>
</ul>

import itertools
import sys
sys.setrecursionlimit(10**8)

from typing import List

class Solution:
    # this version is about O(n^3) time complexity which is a bit slow
    def stoneGameVMemo(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        memo = {}

        def helper(i:int, j:int) -> int:
            if j - i < 1:
                memo[(i, j)] = 0
            if (i, j) in memo:
                return memo[(i, j)]

            t_sum = sum(stoneValue[i:j+1])
            l_sum = 0
            res = 0

            for k in range(i, j):
                l_sum += stoneValue[k]
                r_sum = t_sum - l_sum

                if l_sum <= r_sum:
                    res = max(res, l_sum + helper(i, k))
                if l_sum >= r_sum:
                    res = max(res, r_sum + helper(k+1, j))
                
            memo[(i, j)] = res
            return res

        
        score = helper(0, n-1)
        # print(memo)
        return score
    
    # this version is also O(n^3) time complexity but using dynamic programming
    # variable dp[i][j] is the maximum score the player can get for the stones from i to j
    def stoneGameVDP(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        dp = [[0] * n for _ in range(n)]
        sums = [0] + list(itertools.accumulate(stoneValue))

        # print("stoneValue:", stoneValue)
        # print("sums:", sums)

        # lets think about the simplest case, which is where
        # n = 2, then the maximum score is the minimum of the two
        # equivalently, for an array of length n, the subproblem of
        # length 2 is the base case. First we solve all subproblems
        # of length 2, then 3, then 4, ...
        #
        # for the subproblem of length 2:
        #
        # dp[i][j] = dp[i][i+1], k = i, j = i+1
        # if left <= right:
        #    dp[i][j] = max(dp[i][j], left + dp[i][k])
        #    dp[i][i+1] = max(dp[i][i+1], left + dp[i][i])
        #    dp[i][i+1] = left
        # if left >= right:
        #    dp[i][j] = max(dp[i][j], right + dp[k+1][j])
        #    dp[i][i+1] = max(dp[i][i+1], right + dp[i+1][i+1])
        #    dp[i][i+1] = right
        #
        # so, after this, we have dp[i][i+1] correctly calculated. Next, we want
        # to solve the subproblem of length 3, which is dp[i][i+2]. We just have
        # to make sure that we don't use data from below the diagonal or above the
        # first off-diagonal (e.g. for d[i][j], we can't use d[k][l] where j-i > 1
        # and l-k > 1).
        #
        # dp[i][j] = dp[i][i+2], k = (i, i+1), j = i+2
        # if left <= right:
        #    dp[i][j] = max(dp[i][j], left + dp[i][k])
        #    dp[i][i+2] = max(dp[i][i+2], left + dp[i][i]) <= k = i, j = i+2
        #    dp[i][i+2] = max(dp[i][i+2], left + dp[i][i+1]) <= k = i+1, j = i+2
        # if left >= right:
        #    dp[i][j] = max(dp[i][j], right + dp[k+1][j])
        #    dp[i][i+2] = max(dp[i][i+2], right + dp[i+1][i+2]) <= k = i, j = i+2
        #    dp[i][i+2] = max(dp[i][i+2], right + dp[i+2][i+2]) <= k = i+1, j = i+2
        #
        # so, as we can see, by solving the subproblems in order of length, we make
        # sure that the data we need is already calculated.

        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i + l -1
                for k in range(i, j):
                    l_sum = sums[k+1] - sums[i]
                    r_sum = sums[j+1] - sums[k+1]

                    if l_sum <= r_sum:
                        dp[i][j] = max(dp[i][j], l_sum + dp[i][k])
                    if l_sum >= r_sum:
                        dp[i][j] = max(dp[i][j], r_sum + dp[k + 1][j])
        

        return dp[0][n - 1]
    
    # dynamic programming O(n^2)
    # it turns out that there is a bound for the possible locations of the split
    # this reduces the inner loop to almost O(1) as opposed to O(n)
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        dp = [[0] * n for _ in range(n)]
        bc_l = [[0] * n for _ in range(n)]
        bc_r = [[0] * n for _ in range(n)]
        sums = [0] + list(itertools.accumulate(stoneValue))

        # the bound for where the split can occur is the following:
        # best_cut_loc[i][j-1] - 1 <= best_cut_loc[i][j] <= best_cut_loc[i+1][j] + 1
        # base case: (i, i+1)
        # best_cut_loc[i][i+1-1] - 1 <= best_cut_loc[i][i+1] <= best_cut_loc[i+1][i+1] + 1
        # best_cut_loc[i][i] - 1 <= best_cut_loc[i][i+1] <= best_cut_loc[i+1][i+1] + 1
        # i-1 <= best_cut_loc[i][i+1] <= i+1
        #
        # which makes sense, because for the subproblem of length 2, the split can only
        # occur at i.

        for i in range(n):
            bc_l[i][i] = i
            bc_r[i][i] = i
        
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i + l -1

                # I think I have the bounds wrong. Need to work this out analytically
                idx_left = max(bc_l[i][j-1] - 1, i)
                idx_right = min(bc_r[i+1][j] + 2, j)

                for k in range(idx_left, idx_right):
                    l_sum = sums[k+1] - sums[i]
                    r_sum = sums[j+1] - sums[k+1]

                    if l_sum <= r_sum:
                        if dp[i][j] < l_sum + dp[i][k]:
                            dp[i][j] = l_sum + dp[i][k]
                            bc_r[i][j] = bc_l[i][j] = k
                        elif dp[i][j] == l_sum + dp[i][k]:
                            bc_r[i][j] = max(bc_r[i][j], k)
                            bc_l[i][j] = min(bc_l[i][j], k)
                    if l_sum >= r_sum:
                        if dp[i][j] < r_sum + dp[k+1][j]:
                            dp[i][j] = r_sum + dp[k+1][j]
                            bc_r[i][j] = bc_l[i][j] = k
                        elif dp[i][j] == r_sum + dp[k+1][j]:
                            bc_r[i][j] = max(bc_r[i][j], k)
                            bc_l[i][j] = min(bc_l[i][j], k)

        return dp[0][n - 1]
29400