LeetCode 解題筆記：2904. Shortest and Lexicographically Smallest Beautiful String

作者：王一哲
日期：2026年8月26日


LeetCode 題目連結：2904. Shortest and Lexicographically Smallest Beautiful String

解題想法

中等難度題。題目給一個只有 01 的字串 $s$，要找出 $s$ 之中連續的子字串而且子字串中正好有 $k$ 個 $1$，回傳符合要求的最短子字串，如果有多個長度相同且符合規則的子字串，回傳之中字典序最小者。由於題目要找的是連續子字串，很適合用滑動視窗解題。先用一個 for 迴圈更新視窗右端點 $right$ 從 $0$ 到 $n-1$，先依照 $s[right]$ 更新 $1$ 的數量 $ones$；再用一個 while 迴圈，如果 $ones > k$ 或是 $ones = k$ 且 $s[left] = '0'$，更新 $ones$、再將 $left$ 向右移一格；跑完 while 迴圈之後，如果 $ones = k$，而且子字串長度較短或長度相等但子字串字典序較小就更新答案。由於用 C 語言處理字串很麻煩，我就不寫 C 語言版本了。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 30.63%.

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        # 長度，目前範圍中有幾個1，視窗左端點
        n, ones, left = len(s), 0, 0
        ans = "1" * (n+1)  # 答案，預設為超出上限的字串
        # 滑動視窗，移動右端點
        for right in range(n):
            # 更新範圍內 1 的數量
            if s[right] == '1': ones += 1
            # ones 大於 k 或 ones 等於 k 且 s[left] 是 0
            while ones > k or (ones == k and s[left] == '0'):
                if s[left] == '1': ones -= 1  # 更新範圍內 1 的數量
                left += 1  # 向右移1格
            # 如果 1 的數量等於 k，更新答案
            if ones == k:
                sub = s[left : right + 1]  # 子字串
                length = right - left + 1  # 子字串長度
                # 如果子字串長度較短或長度相等但子字串字典序較小，更新答案
                if length < len(ans) or (length == len(ans) and sub < ans): 
                    ans = sub
        return ans if ans != "1" * (n+1) else ""

LeetCode 解題筆記：3718. Smallest Missing Multiple of K

作者：王一哲
日期：2026年8月25日


LeetCode 題目連結：3718. Smallest Missing Multiple of K

解題想法

簡單題。題目給一個陣列 $nums$ 及一個整數 $k$，要找出不在 $nums$ 之中 $k$ 的倍數最小值。這題可以用集合或是字典記錄 $nums$ 之中的數字；由於測資的範圍不大，也可以用一個長度為 10001 的陣列，將 $nums$ 之中的數字標記為 True。如果用 Python 解題，用 set 及 dict 速度最快；如果用 C 或 C++ 解題，用陣列速度最快。因為答案在 1 到 100 之間，設定一個變數 i，從 1 開始往上線性搜尋就好。

Python 程式碼

set. Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 18.61%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_set = set(nums)
        i = 1
        while i*k in num_set: i += 1
        return i*k

dict. Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 53.35%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_map = {num: True for num in nums}
        i = 1
        while i*k in num_map: i += 1
        return i*k

list. Runtime: 3 ms, beats 20.84%. Memory: 19.17 MB, beats 88.59%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        state = [False] * 10001
        for num in nums: state[num] = True
        i = 1
        while state[i*k]: i += 1
        return i*k

LeetCode 解題筆記：1872. Stone Game VIII

作者：王一哲
日期：2026年8月24日


LeetCode 題目連結：1872. Stone Game VIII

解題想法

困難題。題目給一個陣列 $stones$ 代表一列石頭由左到右的分數，Alice 與 Bob 兩人輪流從左邊拿走 $x$ 個石頭，且 $x > 1$，可以獲得拿走的石頭的總分，然後將一個等於總分的石頭放在最左邊，只剩下一個石頭時遊戲結束，固定由 Alice 先行動。假設 Alice 要使分差最大，Bob 要使分差最小，回傳遊戲結束時的分差。

由於每次行動時會拿走前 $x$ 顆石頭，再將一顆等於總分的石頭放在最左邊，因此下一個人行動時拿到的石頭會包含上一次取走的 $x$ 顆石頭的總分。計算分差時會用到前 $x$ 顆石頭的總分，可以先建立前綴和陣列 $psum$。這題要用動態規畫解題，理論上比較適合由最後的狀態往回推。假設 $dp[i]$ 代表處理 $stones[i]$ 時的最大分差，邊界條件為最後一次行動時會拿走所有的石頭，也就是 $i = n-1$ 時 $dp[i] = psum[n-1]$。更新狀態時有兩種可能性：

1. 拿走 $stones[i]$，最大分差為 $psum[i] - dp[i+1]$
2. 不拿 $stones[i]$，最大分差為 $dp[i+1]$

更新時最這兩者之中較大者。由於更新時只需要用到 $dp[i+1]$ 的值，可以不需要建立完整的陣列，只要用一個變數 $dp$ 記錄最大分差，用 $dp = max(psum[i] - dp, dp)$ 更新就好。

另一個寫法是由 $i = 0$ 開始處理，並用記憶化及遞迴往下找 $i + 1$ 的狀態，直到 $i = n-1$ 時結束遞迴。如果在 Python 用這個寫法，必須引入 sys 函式庫，並用 sys.setrecursionlimit(200000) 調整遞迴深度，否則會遇到遞迴深度過深的問題。

Python 程式碼

方法1。Runtime: 674 ms, beats 65.09%. Memory: 32.25 MB, beats 98.22%.

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # 建立前綴和陣列
        n = len(stones)
        psum = stones[:]
        for i in range(1, n):
            psum[i] += psum[i-1]
        """
         動態規畫，dp[i] 代表選擇索引值 i 的最大分差，由最後的狀態往前推
         狀況1，選擇拿 psum[i]，下一個狀態的 dp[i+1]，目前最大分差為 psum[i] - dp[i+1]
         狀況2，不拿 psum[i]，目前最大分差為 dp[i+1]
        """
        dp = psum[-1]  # 邊界條件，最後一次要全部拿走
        for i in range(n-2, 0, -1):  # 只跑 i = n-2 ~ 1，因為一次至少拿 2 個石頭
            dp = max(psum[i] - dp, dp)
        return dp

方法2。Runtime: 770 ms, beats 14.20%. Memory: 83.57 MB, beats 11.24%.

import sys
sys.setrecursionlimit(200000)  # 調整遞迴深度

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        # 建立前綴和陣列
        n = len(stones)
        psum = stones[:]
        for i in range(1, n):
            psum[i] += psum[i-1]

        # 記憶化及遞迴
        memo = [None] * n

        def dfs(i):  # 目前選擇索引值 i
            # 遞迴出口，最後一次只能全拿
            if i == n-1:
                return psum[-1]
            # 如果 memo 之中有已經算過的值，直接回傳
            if memo[i] is not None:
                return memo[i]
            # 狀態轉移
            skip = dfs(i+1)  # 不拿 psum[i]
            take = psum[i] - skip  # 拿 psum[i]
            memo[i] = max(take, skip)  # 選擇較大者
            return memo[i]

        # 呼叫 dfs，代入 i = 1，因為至少要拿 2 顆石頭
        return dfs(1)

LeetCode 解題筆記：1927. Sum Game

作者：王一哲
日期：2026年8月23日


LeetCode 題目連結：1927. Sum Game

解題想法

中等難度題。題目給一個字串 $num$，其中只包含數字 0 ~ 9 及 ?，Alice 和 Bob 兩個人輪流行動，由 Alice 先行動，每次行動時可以將一個問𢛶山改成 0 ~ 9 之中的一個數字。如果最後 $num$ 的左半邊加總等於右半邊的加總則 Bob 獲勝，回傳 False；反之則 Alice 獲勝，回傳 True。這題困難的地方在於分析勝敗條件，程式碼反而很簡單。

如果 Bob 要獲勝，第一個條件是左、右兩側的問號數量必須相同，如果數量不同，Alice 會多行動一次，一次可以讓兩側的加總不相等。第二個條件是兩側的問號數量差乘以 9 必須等於兩側總和差乘以 2。先考慮兩側都有問號的狀況，如果 Alice 將左側一個問號改成數字 $x$，Bob 可以將右側的一個問號也改成數字 $x$，兩者的效果就會抵消。再考慮同側問號的狀況，因為 Alice 會盡量讓兩側加總差異越大越好，假設改成 $x$，Bob 為了讓兩側加總相等，會將同側另一個問號改成 $9 - x$。假設右側問號比左側問號多 $\Delta q$ 個，則多出來的問號產生的數字加總必須等於左側數字加總減去右側數字加總 $$ \frac{\Delta q}{2} \times 9 = lsum - rsum \Rightarrow \Delta q \times 9 = (lsum - rsum) \times 2 $$

Python 程式碼

Runtime: 59 ms, beats 50.00%. Memory: 19.68 MB, beats 98.82%.

class Solution:
    def sumGame(self, num: str) -> bool:
        # 1. 計算左、右兩側數字加總、問號數量
        n = len(num)  # 長度
        lsum, rsum = 0, 0  # 左側數字加總，右側數字加總
        lque, rque = 0, 0  # 左側問號數量，右側問號數量
        for i in range(n//2):
            if num[i] == '?':
                lque += 1
            else:
                lsum += int(num[i])
        for i in range(n//2, n):
            if num[i] == '?':
                rque += 1
            else:
                rsum += int(num[i])
        # 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝
        if (lque + rque) % 2 == 1: return True
        # 3. dq = rque - lque，同側每一對問號可以產生數字總和 9
        # 必須抵消 lsum - rsum，Bob 才會獲勝
        return (rque - lque) * 9 != (lsum - rsum) * 2

LeetCode 解題筆記：3622. Check Divisibility by Digit Sum and Product

作者：王一哲
日期：2026年8月22日


LeetCode 題目連結：3622. Check Divisibility by Digit Sum and Product

解題想法

簡單題。題目給一個整數 $n$，假設 $n$ 的每個數字相加為 $dsum$，每個數字相乘為 $prod$，回傳 $n$ 是否可以被 $dsum + prod$ 整除。建立變數 $x = n$、$dsum = 0$、$prod = 1$，用一個 while 迴圈取出 $x$ 的每個數字，計算 $dsum$ 及 $prod$，最後回傳 $n % (dsum + prod) == 0$。也可以將 $n$ 轉成字串 $s$，再依序由 $s$ 讀取每個位數的字元，計算 $prod$ 及 $dsum$，速度也很快。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.34 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        x, prod, dsum = n, 1, 0
        while x:
            d = x % 10
            x //= 10
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 24.05%.

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s = str(n)
        prod, dsum = 1, 0
        for c in s:
            d = int(c)
            prod *= d
            dsum += d
        return n % (prod + dsum) == 0

LeetCode 解題筆記：554. Brick Wall

作者：王一哲
日期：2026年8月21日


LeetCode 題目連結：554. Brick Wall

解題想法

中等難度題。題目給一個 $n$ 列的二維陣列 $wall$，每一列代表這列之中由左到右每個磚塊的寬度，題目假設要從地面往上畫一條鉛直線，這條線穿過的磚塊數量最少為幾塊。這題要反過來寫，先找出磚塊之間的接縫位置，計算接縫位置的數量，答案就是 $n$ 減去接縫數量的最小值。由於每列的總寬度極大，但是接縫數量不會太大，很適合用字典計數。用 C++ 解題要注意，接縫的位置會超出 int 的上限，要用 long 才不會溢位。

Python 程式碼

使用預設的 dict。Runtime: 3 ms, beats 93.16%. Memory: 22.97 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = dict()  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                if pos not in psum:
                    psum[pos] = 1
                else:
                    psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

使用 collections.defaultdict。Runtime: 7 ms, beats 70.30%. Memory: 22.92 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = defaultdict(int)  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

LeetCode 解題筆記：3069. Distribute Elements Into Two Arrays I

作者：王一哲
日期：2026年8月20日


LeetCode 題目連結：3069. Distribute Elements Into Two Arrays I

解題想法

簡單題。題目給一個長度 $n$ 的陣列 $nums$，依序從 $nums$ 讀取數據，先將 $nums[0]$ 存到陣列 $arr1$，將 $nums[1]$ 存到陣列 $arr2$，接下來 $nums[2]$ 到 $nums[n-1]$ 則是依照 $arr1, arr2$ 的末項決定要接在哪一個陣列的後面，如果 $arr1$ 末項大於 $arr2$ 末項，則 $nmus$ 取出的數字接在 $arr1$ 後面，反之則接在 $arr2$ 後面。最後再將 $arr2$ 接在 $arr1$ 後面，回傳 $arr1$。基本上只要按照題目要求操作即可，如果用 Python list 或是 C++ vector 可以改變長度，寫起來很方便；如果用 C array 則要記錄目前儲存資料的索引值，會比較麻煩一點。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 61.54%.

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1, arr2 = [nums[0]], [nums[1]]
        n = len(nums)
        for i in range(2, n):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        return arr1 + arr2

Runtime: 0 ms, beats 100.00%. Memory: 19.31 MB, beats 22.76%.

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        arr1, arr2 = [0]*n, [0]*n
        arr1[0] = nums[0]
        arr2[0] = nums[1]
        i, j = 0, 0
        for k in range(2, n):
            if arr1[i] > arr2[j]:
                i += 1
                arr1[i] = nums[k]
            else:
                j += 1
                arr2[j] = nums[k]
        for k in range(j+1):
            i += 1
            arr1[i] = arr2[k]
        return arr1

LeetCode 解題筆記：1386. Cinema Seat Allocation

作者：王一哲
日期：2026年8月19日


LeetCode 題目連結：1386. Cinema Seat Allocation

解題想法

中等難度的題目。題目給一個二維陣列 $reservedSeats$，其中每一個元素有兩項，分別代表第幾列、第幾個座位已經被預約。所有的座位共有 $n$ 列，每列有編號 1 到 10 的座位。如果有 4 個人一組的客人，只能被安排在 $(2, 3, 4, 5)$、$(4, 5, 6, 7)$ 或 $(6, 7, 8, 9)$ 而且沒有被預約的座位。題目要計算最多可以安排幾組 4 個人的客人。由於這題的 $n$ 最大可以到 $10^9$，如果建一個 $n \times n$ 的陣列並標記每個座位是否被預約，這樣會超出記憶體上限。但是這題的 $reserveSeats$ 的長度最大值是 $10 \times n$ 及 $10^4$ 之中較小者，實際上需要標記的被預約座位並不多，可以用字典 $reserved$ 儲存已預約座位的列狀態就好。甚至可以進一步用二進位 bitmask 記錄座位狀態，用 0 代表空位，用 1 代表被預約的座位，例如 $0b00000111100$ 代表第 2、3、4、5 號座位被預約，這樣可以節省記憶體，而且用 bitwise 操作速度很快。

計算答案時，先處理整列都是空位的部分，每一列可以放入 2 組人，因此答案 $ans = (n - len(reservec)) \times 2$。再從 $reserved$ 讀取有被預約的座位狀態 $mask$，如果 $0b00000111100 & mask == 0$ 代表可以將這組人放入 $(2, 3, 4, 5)$ 號座位；如果 $0b01111000000 & mask == 0$ 代表可以將這組人放入 $(6, 7, 8, 9)$ 號座位；如果 $0b00011110000 & mask == 0$ 代表可以將這組人放入 $(4, 5, 6, 7)$ 號座位。如果同時可以放入 $(2, 3, 4, 5)$ 及 $(6, 7, 8, 9)$ 號座位，答案加 2；如果以上 3 種狀態任何 1 種成立，答案加 1。

Python 程式碼

用 defaultdict 寫起來比較方便，但是速度比較慢。Runtime: 30 ms, beats 78.66%. Memory: 22.95 MB, beats 53.73%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用字典儲存每列已經預約的座位
        reserved = defaultdict(int)
        for r, c in reservedSeats:
            reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

用預設的 dict 寫起來比較麻煩，但是速度比較快。Runtime: 19 ms, beats 97.43%. Memory: 22.50 MB, beats 94.60%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用預設的字典儲存每列已經預約的座位
        reserved = dict()
        for r, c in reservedSeats:
            if r not in reserved:
                reserved[r] = (1 << c)
            else:
                reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

LeetCode 解題筆記：3471. Find the Largest Almost Missing Integer

作者：王一哲
日期：2026年8月18日


LeetCode 題目連結：3471. Find the Largest Almost Missing Integer

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，要從 $nums$ 之中找出長度為 $k$ 的連續子序列，子序列之中有一個數字只出現一次，回傳這些數字中的最大值。我一開始用的寫法非常直接，先找出所有長度為 $k$ 的連續子序列，將子序列存成 set，再將 set 存入 list 之中。接下來再依序從 $nums$ 讀取數字 $num$，檢查 $num$ 是否在所有的子序列中只出現一次而且 $num$ 大於目前的答案 $ans$，如果條件成立就更新 $ans$。這個寫法在 Python 的速度還可以，但是在 C++ 就很糟糕了。

比較好的寫法應該是列出以下 3 種狀況：

1. $k = n$，子序列就是 $nums$，回傳 $nums$ 之中的最大值。
2. $k = 1$，子序列就是 $nums$ 之中的每個數字，找出只在 $nums$ 之中出現一次的數字最大值。
3. $k \neq n, k \neq 1$，只需要找 $nums[0]$ 與 $nums[n-1]$，因為中間的數字至少會出現在 2 個子序列之中。答案有 4 種：
   1. $nums[0]$ 與 $nums[n-1]$ 都只出現一次，回傳較大者。
   2. $nums[0]$ 只出現一次，$nums[n-1]$ 出現 2 次以上，回傳 $nums[0]$。
   3. $nums[n-1]$ 只出現一次，$nums[0]$ 出現 2 次以上，回傳 $nums[n-1]$。
   4. 以上條件皆不成立，回傳 $-1$。

Python 程式碼

方法1，Runtime: 3 ms, beats 62.30%. Memory: 19.15 MB, beats 93.85%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        subs = [set() for _ in range(n-k+1)]
        for i in range(n-k+1):
            subs[i] = set(nums[i:i+k])

        ans = -1
        for num in nums:
            cnt = 0
            for sub in subs:
                if num in sub: cnt += 1
                if cnt >= 2: break
            if cnt == 1 and num > ans:
                ans = num
        return ans

方法2，Runtime: 1 ms, beats 70.90%. Memory: 19.36 MB, beats 35.66%.

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        # Case 1. k == n，回傳 nums 的最大值
        if k == n: return max(nums)

        # Case 2. k == 1，回傳只出現一次的數字最大值
        cnt = Counter(nums)  # 計數器
        if k == 1:
            ans = -1  # 答案預設為 -1
            for num in nums:
                if cnt[num] == 1 and num > ans:
                    ans = num
            return ans
        
        # Case 3. 一般狀況，只需要考慮 nums[0] 及 nums[n-1]，因為其它數字至少會出現在子序列之中 2 次
        first, last = nums[0], nums[-1]
        # first, last 次數都是 1，回傳較大者
        if cnt[first] == 1 and cnt[last] == 1:
            return max(first, last)
        # first 次數 1，last 次數大於 1，回傳 first
        if cnt[first] == 1 and cnt[last] > 1:
            return first
        # first 次數大於 1，last 次數 1，回傳 last
        if cnt[first] > 1 and cnt[last] == 1:
            return last
        # 沒有答案，回傳 -1
        return -1

LeetCode 解題筆記：1563. Stone Game V

作者：王一哲
日期：2026年8月17日


LeetCode 題目連結：1563. Stone Game V

解題想法

困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，個回合 Alice 可以選擇一個分割點，將這列石頭分成左、右半邊，Bob 會將總分較高的半邊丢掉，Alice 可以獲得留下半邊石頭的總分，題目要問 Alice 最多可以拿幾分。由於這個題目需要不斷地計算區問和，需要先建立前綴和陣列 $psum$。接下來用動態規畫解題，定義大小為 $n \times n$ 的二維陣列 $dp$，$dp[i][j]$ 代表 Alice 在區間 i ~ j 能獲得的最高分，最後答案會在 $dp[0][n-1]$。填滿 $dp$ 的方法有兩種，第一種較簡單但是時間複雜度為 $O(n^3)$，用 Python 會超時，C 與 C++ 可以過關，但是時間排名很後面；第二種較複雜但是時間複雜度為 $O(n^2)$，用 Python、C、C++ 都能過關。

Python 程式碼

方法1，超時。

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)  # 數量
        
        # 1. 建立前綴和，之後可以用來查詢區間和
        psum = [0] * (n+1)  # pusm 的索引值比 stoneValue 多 1
        for i in range(1, n+1):
            psum[i] = psum[i-1] + stoneValue[i-1]
        
        # 2. 建立動態規畫陣列，dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
        dp = [[0]*n for _ in range(n)]
        
        # 3. 動態規畫
        for length in range(2, n+1):  # 區間長度 2 ~ n
            for i in range(0, n - length + 1):  # 起點 0 ~ n - length
                j = i + length - 1  # 終點
                for k in range(i, j):  # 分割點 i ~ j-1
                    lsum = psum[k+1] - psum[i]  # stoneValue[i] ~ stoneValue[k]
                    rsum = psum[j+1] - psum[k+1]  # stoneValue[k+1] ~ stoneValue[j]
                    if lsum > rsum:  # 左半邊總分較多，剩下右半邊
                        dp[i][j] = max(dp[i][j], rsum + dp[k+1][j])
                    elif lsum < rsum:  # 右半總分較多，剩下左半邊
                        dp[i][j] = max(dp[i][j], lsum + dp[i][k])
                    else:  # 兩側分數相同，Alice 選 dp 區間較高分
                        dp[i][j] = max(dp[i][j], lsum + max(dp[i][k], dp[k+1][j]))
        # 答案在 dp[0][n-1]
        return dp[0][n-1]

方法2，Runtime: 619 ms, beats 77.25%. Memory: 33.17 MB, beats 65.49%.

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)  # 數量
        
        # 1. 建立前綴和，之後可以用來查詢區間和
        psum = [0] * (n+1)  # pusm 的索引值比 stoneValue 多 1
        for i in range(1, n+1):
            psum[i] = psum[i-1] + stoneValue[i-1]
        
        # 2. 建立動態規畫陣列
        # dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
        dp = [[0]*n for _ in range(n)]
        # lmax[i][j] = dp[i][k] + sum(dp[i:k+1]) 的最大值
        lmax = [[0]*n for _ in range(n)]
        # rmax[i][j] = dp[k][j] + sum(dp[k:j+1]) 的最大值
        rmax = [[0]*n for _ in range(n)]
        # 初始化 lmax, rmal，長度 1 
        for i in range(n):
            lmax[i][i] = stoneValue[i]
            rmax[i][i] = stoneValue[i]
        
        # 3. 動態規畫，由短至長
        for i in range(n-1, -1, -1):  # i = n-1 ~ 0
            mid = i - 1  # 分割點
            for j in range(i+1, n):  # j = i+1 ~ n-1
                total = psum[j+1] - psum[i]  # stoneValue[i] + ... + stoneValue[j]
                # 找出左半邊和 L 大於右半邊和 R 的分割點
                # 如果 mid + 1 這格還是不符合條件，再向右移動1格
                # L >= R => L + L >= L + R => 2*L >= total
                # 2 * (psum[mid + 2] - psum[i]) >= total
                while mid + 1 < j and 2 * (psum[mid + 2] - psum[i]) <= total:
                    mid += 1
                
                res = 0
                # 狀況1，左半邊總分 > 右半邊總分 
                if mid >= i:
                    res = max(res, lmax[i][mid])
                    # mid 左半邊總分 == 右半邊總分，可以留下右半邊
                    if 2 * (psum[mid + 1] - psum[i]) == total:
                        res = max(res, rmax[mid + 1][j])
                # 狀況2，左半邊總分 < 右半邊總分
                if mid + 2 <= j:
                    res = max(res, rmax[mid + 2][j])
                # 更新 dp, lmax, rmax
                dp[i][j] = res
                lmax[i][j] = max(lmax[i][j-1], dp[i][j] + total)
                rmax[i][j] = max(rmax[i+1][j], dp[i][j] + total)
        # 答案在 dp[0][n-1]
        return dp[0][n-1]