Stone Game Python Solution with Tests

lcpy gen -n 877   # by problem number
lcpy gen -s stone_game   # by problem name

Input: piles = [5,3,4,5]
Output: true
Explanation:
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.

Input: piles = [3,7,2,3]
Output: true

class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def stone_game(self, piles: list[int]) -> bool:
        n = len(piles)
        # dp[i][j] = max net advantage current player can secure from piles[i..j]
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = piles[i]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                pick_left = piles[i] - dp[i + 1][j]
                pick_right = piles[j] - dp[i][j - 1]
                dp[i][j] = max(pick_left, pick_right)
        return dp[0][n - 1] > 0