There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
In each round of the game, Alice divides the row into two non-empty rows (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’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.
The game ends when there is only one stone remaining. Alice’s score is initially zero.
Return the maximum score that Alice can obtain.
條件
- Alice 將石堆左右分開，將較小堆總和加入總分
- Alice 需盡可能拿到最高分
解題方式：
- 利用 dp 避免重複計算
- 先算好 prefix sum，執行時就不需重複計算石堆加總
Source Code
def stoneGameV(self, stoneValue: List[int]) -> int:
n = len(stoneValue)
if n == 1:
return 0 # 無法分成兩個區段，得分為 0
# 為避免重複加總，先算好 prefix sum 方便計算
prev_sum = [0]
for value in stoneValue:
prev_sum.append(prev_sum[-1]+value)
dp = [[-1 for _ in range(n)]for _ in range(n)] # 紀錄每個區間的最大得分，-1 表示未計算
def find_max(left, right):
"""
計算 stoneValue[left:right+1] 區間，Alice 能取得的最高總分
"""
if left >= right:
return 0
if dp[left][right] < 0:
# 進行計算
ans = 0
left_sum = 0
right_sum = prev_sum[right+1] - prev_sum[left]
for i in range(left, right):
left_sum += stoneValue[i]
right_sum -= stoneValue[i]
if left_sum < right_sum:
# Alice keeps left side
ans = max(ans, left_sum + find_max(left, i))
elif left_sum > right_sum:
# Alice keeps right side
ans = max(ans, right_sum + find_max(i + 1, right))
else:
# 兩邊相等，兩邊的結果皆須考慮
ans = max(ans, left_sum + find_max(left, i), right_sum + find_max(i + 1, right))
dp[left][right] = ans
# 回傳計算結果
return dp[left][right]
find_max(0, n-1)
return dp[0][n-1]