LeetCode 5766. 石子游戏 VIII
原题链接
困难
作者:
ITNXD
,
2021-05-25 20:23:06
,
所有人可见
,
阅读 228
详细请查看注释内容
参考代码:
class Solution {
/*
状态表示:f[i]表示从i到n中选择一个位置j,使得 s[j] -(下一轮对手得分)最大的最大值!(下标从1开始)
状态计算:
Alice不选i:f[i + 1](则只能从i + 1及后面选)
Alice选 i:s[i] - f[i + 1](我选i,你只能选 i + 1及后面)
f[i] = max(f[i + 1], s[i] - f[i + 1]);
s[]为前缀和数组!
注意:
1. 由于f[i]要用到f[i + 1],因此我们可以倒序计算循环
2. 最后一项f[n]要用到f[n + 1],显然f[n + 1]不合法,因此单独处理,f[n] = s[n]
优化:(自己修改即可)
1. 由于f[i]只用到f[i + 1],所以不必要开一个数组,直接变量迭代即可!
2. 由于前缀和也是用了s[i],再用s[i - 1],因此也可以用变量替换进行迭代即可!
*/
public:
int stoneGameVIII(vector<int>& stones) {
int n = stones.size();
vector<int> s(n + 1), f(n + 1);
for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + stones[i - 1];
f[n] = s[n];
// 最少选择两个 i >= 2
for(int i = n - 1; i >= 2; i --) f[i] = max(s[i] - f[i + 1], f[i + 1]);
// 最终答案:从2 ~ n中选的最大分数差!f[2]
return f[2];
}
};