日期：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]
C++ 程式碼
方法1，Runtime: 1002 ms, beats 11.40%. Memory: 27.72 MB, beats 33.99%.
class Solution {
public:
int stoneGameV(vector<int>& stoneValue) {
int n = (int)stoneValue.size(); // 數量
/* 1. 建立前綴和，之後可以用來查詢區間和 */
vector<int> psum (n+1, 0); // pusm 的索引值比 stoneValue 多 1
for(int i = 1; i <= n; i++) {
psum[i] = psum[i-1] + stoneValue[i-1];
}
/* 2. 建立動態規畫陣列，dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分 */
vector<vector<int>> dp (n, vector<int> (n, 0));
/* 3. 動態規畫 */
for(int length = 2; length <= n; length++) { // 區間長度 2 ~ n
for(int i = 0; i <= n - length; i++) { // 起點 0 ~ n - length
int j = i + length - 1; // 終點
for(int k = i; k < j; k++) { // 分割點 i ~ j-1
int lsum = psum[k+1] - psum[i]; // stoneValue[i] ~ stoneValue[k]
int 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]);
} else if (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: 47 ms, beats 96.82%. Memory: 54.48 MB, beats 5.08%.
class Solution {
public:
int stoneGameV(vector<int>& stoneValue) {
int n = (int)stoneValue.size(); // 數量
/* 1. 建立前綴和，之後可以用來查詢區間和 */
vector<int> psum (n+1, 0); // pusm 的索引值比 stoneValue 多 1
for(int i = 1; i <= n; i++) {
psum[i] = psum[i-1] + stoneValue[i-1];
}
/* 2. 建立動態規畫陣列 */
// dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
vector<vector<int>> dp (n, vector<int> (n, 0));
// lmax[i][j] = dp[i][k] + sum(dp[i:k+1]) 的最大值
vector<vector<int>> lmax (n, vector<int> (n, 0));
// rmax[i][j] = dp[k][j] + sum(dp[k:j+1]) 的最大值
vector<vector<int>> rmax (n, vector<int> (n, 0));
// 初始化 lmax, rmal，長度 1
for(int i = 0; i < n; i++) {
lmax[i][i] = stoneValue[i];
rmax[i][i] = stoneValue[i];
}
/* 3. 動態規畫，由短至長 */
for(int i = n-1; i >= 0; i--) { // i = n-1 ~ 0
int mid = i - 1; // 分割點
for(int j = i+1; j < n; j++) { // j = i+1 ~ n-1
int 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) && (2 * (psum[mid + 2] - psum[i]) <= total)) {
mid++;
}
int res = 0;
// 狀況1，左半邊總分 > 右半邊總分
if (mid >= i) {
res = max(res, lmax[i][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];
}
};
C 語言程式碼
方法1，Runtime: 1264 ms, beats 5.56%. Memory: 10.06 MB, beats 94.44%.
int stoneGameV(int* stoneValue, int stoneValueSize) {
/* 1. 前立前綴和，用於查詢區間和 */
int n = stoneValueSize, psum[501] = {0};
for(int i = 0; i < n; i++) {
psum[i+1] = psum[i] + stoneValue[i];
}
/* 2. 動態規畫陣列，dp[i][j] 代表區間 i ~ j Alice 能拿到的最高分 */
int dp[501][501];
memset(dp, 0, sizeof(dp));
/* 3. 動態規畫填滿 dp */
for(int length = 2; length <= n; length++) { // 長度 2 ~ n
for(int i = 0; i <= n - length; i++) { // 起點 0 ~ n - length
int j = i + length - 1; // 終點
for(int k = i; k < j; k++) { // 分割點 i ~ j-1
int lsum = psum[k+1] - psum[i]; // 左側總分
int rsum = psum[j+1] - psum[k+1]; // 右側總分
if (lsum > rsum) { // 左側總分較高，留右側
if (rsum + dp[k+1][j] > dp[i][j]) { // 取右側後總分變高
dp[i][j] = rsum + dp[k+1][j];
}
} else if (lsum < rsum) { // 右側總分較高，留左側
if (lsum + dp[i][k] > dp[i][j]) { // 取右側後總分變高
dp[i][j] = lsum + dp[i][k];
}
} else { // 兩側分數相同，選高分的
int imax = dp[i][k];
if (dp[k+1][j] > imax) {
imax = dp[k+1][j];
}
if (lsum + imax > dp[i][j]) {
dp[i][j] = lsum + imax;
}
}
}
}
}
return dp[0][n-1];
}
方法2，Runtime: 39 ms, beats 88.89%. Memory: 12.05 MB, beats 55.56%.
#define max(a, b) ((a) > (b) ? (a) : (b))
int stoneGameV(int* stoneValue, int stoneValueSize) {
int n = stoneValueSize; // 數量
/* 1. 建立前綴和，之後可以用來查詢區間和 */
int psum[501] = {0}; // pusm 的索引值比 stoneValue 多 1
for(int i = 1; i <= n; i++) {
psum[i] = psum[i-1] + stoneValue[i-1];
}
/* 2. 建立動態規畫陣列 */
// dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
// lmax[i][j] = dp[i][k] + sum(dp[i:k+1]) 的最大值
// rmax[i][j] = dp[k][j] + sum(dp[k:j+1]) 的最大值
int dp[501][501], lmax[501][501], rmax[501][501];
memset(dp, 0, sizeof(dp));
memset(lmax, 0, sizeof(lmax));
memset(rmax, 0, sizeof(rmax));
// 初始化 lmax, rmal，長度 1
for(int i = 0; i < n; i++) {
lmax[i][i] = stoneValue[i];
rmax[i][i] = stoneValue[i];
}
/* 3. 動態規畫，由短至長 */
for(int i = n-1; i >= 0; i--) { // i = n-1 ~ 0
int mid = i - 1; // 分割點
for(int j = i+1; j < n; j++) { // j = i+1 ~ n-1
int 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) && (2 * (psum[mid + 2] - psum[i]) <= total)) {
mid++;
}
int res = 0;
// 狀況1，左半邊總分 > 右半邊總分
if (mid >= i) {
res = max(res, lmax[i][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];
}
沒有留言:
張貼留言