class Solution {
public:
int stoneGameVII(vector<int>& stones) {
}
};
1690. 石子游戏 VII
石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。
鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。
示例 1：
输入：stones = [5,3,1,4,2] 输出：6 解释： - 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。 - 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。 - 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。 - 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。 - 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。 得分的差值 18 - 12 = 6 。
示例 2：
输入：stones = [7,90,5,1,100,10,10,2] 输出：122
提示：
n == stones.length2 <= n <= 10001 <= stones[i] <= 1000原站题解
rust 解法, 执行用时: 17 ms, 内存消耗: 2.3 MB, 提交时间: 2024-02-03 23:26:18
impl Solution {
pub fn stone_game_vii(stones: Vec<i32>) -> i32 {
let n = stones.len();
let mut s = vec![0; n + 1];
for (i, &x) in stones.iter().enumerate() {
s[i + 1] = s[i] + x;
}
let mut f = vec![0; n];
for i in (0..n - 1).rev() {
for j in i + 1..n {
f[j] = (s[j + 1] - s[i + 1] - f[j]).max(s[j] - s[i] - f[j - 1]);
}
}
f[n - 1]
}
}
javascript 解法, 执行用时: 101 ms, 内存消耗: 50.7 MB, 提交时间: 2024-02-03 23:26:05
/**
* @param {number[]} stones
* @return {number}
*/
var stoneGameVII = function(stones) {
const n = stones.length;
const s = Array(n + 1);
s[0] = 0;
for (let i = 0; i < n; i++) {
s[i + 1] = s[i] + stones[i];
}
const f = Array(n).fill(0);
for (let i = n - 2; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
f[j] = Math.max(s[j + 1] - s[i + 1] - f[j], s[j] - s[i] - f[j - 1]);
}
}
return f[n - 1];
};
golang 解法, 执行用时: 20 ms, 内存消耗: 3.2 MB, 提交时间: 2024-02-03 23:25:50
func stoneGameVII(stones []int) int {
n := len(stones)
s := make([]int, n+1)
for i, x := range stones {
s[i+1] = s[i] + x
}
f := make([]int, n)
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[j] = max(s[j+1]-s[i+1]-f[j], s[j]-s[i]-f[j-1])
}
}
return f[n-1]
}
java 解法, 执行用时: 20 ms, 内存消耗: 42.2 MB, 提交时间: 2024-02-03 23:25:35
class Solution {
public int stoneGameVII(int[] stones) {
int n = stones.length;
int[] s = new int[n + 1];
for (int i = 0; i < n; i++) {
s[i + 1] += s[i] + stones[i];
}
int[] f = new int[n];
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
f[j] = Math.max(s[j + 1] - s[i + 1] - f[j], s[j] - s[i] - f[j - 1]);
}
}
return f[n - 1];
}
}
python3 解法, 执行用时: 1391 ms, 内存消耗: 16.8 MB, 提交时间: 2024-02-03 23:24:27
class Solution:
def stoneGameVII(self, stones: List[int]) -> int:
n = len(stones)
s = list(accumulate(stones, initial=0))
f = [0] * n
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
f[j] = max(s[j + 1] - s[i + 1] - f[j], s[j] - s[i] - f[j - 1])
return f[-1]
def stoneGameVII2(self, stones: List[int]) -> int:
s = list(accumulate(stones, initial=0)) # 前缀和
@cache # 缓存装饰器，避免重复计算 dfs 的结果
def dfs(i: int, j: int) -> int:
if i == j: # 递归边界
return 0
return max(s[j + 1] - s[i + 1] - dfs(i + 1, j), s[j] - s[i] - dfs(i, j - 1))
ans = dfs(0, len(stones) - 1)
dfs.cache_clear() # 防止爆内存
return ans
def stoneGameVII3(self, stones: List[int]) -> int:
n = len(stones)
s = list(accumulate(stones, initial=0))
f = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
f[i][j] = max(s[j + 1] - s[i + 1] - f[i + 1][j], s[j] - s[i] - f[i][j - 1])
return f[0][-1]
java 解法, 执行用时: 34 ms, 内存消耗: 49.8 MB, 提交时间: 2022-12-11 11:50:19
import static java.lang.Math.*;
class Solution {
public int stoneGameVII(int[] stones) {
int n = stones.length;
int[] pre = new int[n + 1];
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + stones[i - 1];
int[][] f = new int[n + 1][n + 1];
for (int len = 2; len <= n; ++len) {
for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
f[i][j] = max(pre[j] - pre[i] - f[i + 1][j], pre[j - 1] - pre[i - 1] - f[i][j - 1]);
}
}
return f[1][n];
}
}
python3 解法, 执行用时: 2700 ms, 内存消耗: 38 MB, 提交时间: 2022-12-11 11:49:20
'''
dp[i][j] = max(sum(stones[i+1:j]) − dp[i+1][j], sum(stones[i:j]) − dp[i][j−1])
我们使用dp[i][j]表示 i-j堆的得分最大差值，那么下一阶段的转移即为这个阶段的得分-上一阶段的差的最大值
因为sum复杂度为O(n)所以使用前缀和将复杂度降为O(1)
'''
class Solution:
def stoneGameVII(self, nums: List[int]) -> int:
n = len(nums)
presum = [0] * (n+1)
for i in range(1,n+1):
presum[i] = nums[i-1] + presum[i-1]
dp = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
l = presum[j+1] - presum[i+1]
r = presum[j] - presum[i]
dp[i][j] = max(l-dp[i + 1][j], r-dp[i][j-1])
return dp[0][n-1]
cpp 解法, 执行用时: 220 ms, 内存消耗: 82.4 MB, 提交时间: 2022-12-11 11:47:23
// 对于 dp[i][j] 定义为区间 [i,j] 我们要的结果，在区间 [i, j]，dp[i][j] = 先手的总分 - 后手的总分
class Solution {
public:
int stoneGameVII(vector<int>& stones) {
vector<vector<int>>dp(stones.size(), vector<int>(stones.size(),0));
vector<int>sums(stones.size() + 1, 0);
for(int i = 0;i < stones.size();++i)
sums[i + 1] = sums[i] + stones[i];
for(int i = dp.size() - 2;i >= 0;--i){
for(int j = i + 1;j < dp[i].size();++j)
dp[i][j] = max(sums[j + 1] - sums[i + 1] - dp[i + 1][j], sums[j] - sums[i] - dp[i][j - 1]);
}
return dp.front().back();
}
};
cpp 解法, 执行用时: 396 ms, 内存消耗: 154.8 MB, 提交时间: 2022-12-11 11:46:13
/**
* sum[i][j]：表示从 i 到 j 的石头价值总和
* dp[i][j]：表示剩下的石头堆为 i 到 j 时，当前玩家与另一个玩家得分差的最大值，当前玩家不一定是先手Alice
* 状态转移方程：
* 最初始的时候：i == j ，dp[i][j] = 0，因为删了之后没得取
* 当 j - i == 1 时，dp[i][j] = max(stones[i], stones[j])，因为我要利益最大化，我肯定删掉一个较小的石头，取最大得分，反正下一个人是没分的
* 当 j - i > 1 时， dp[i][j] = max(sum[i + 1][j] - dp[i + 1][j], sum[i][j - 1] - dp[i][j - 1])
**/
class Solution {
public:
int stoneGameVII(vector<int>& stones) {
int n = stones.size();
vector<vector<int>> sum(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
if(i == j) sum[i][j] = stones[i]; //记录区间和
else sum[i][j] = stones[j] + sum[i][j - 1];
}
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = n - 1; i >= 0; i--){
for(int j = i + 1; j < n; j++){
dp[i][j] = max(sum[i + 1][j] - dp[i + 1][j], sum[i][j - 1] - dp[i][j - 1]);
}
}
return dp[0][n - 1]; //返回A能取的最大和
}
};