本文主要是介绍LC 1690. 石子游戏 VII,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1690. 石子游戏 VII
难度: 中等
题目大意:
石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。
有
n
块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时,得分较高者获胜。鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。
给你一个整数数组
stones
,其中stones[i]
表示 从左边开始 的第i
个石头的值,如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值 。提示:
n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000
示例 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 。
分析
假设爱丽丝最终的得分是A
鲍勃的得分是B
,那么二者的差值是A - B
,爱丽丝要最大限度扩大这个数字,鲍勃要尽可能减小得分的差值,换句话说就是要B - A
要尽可能扩大这个数字,也就是说要尽可能扩大自己的得分减去对手的得分,以示例1为例,假设爱丽丝第一轮移走了第一个石子,那么剩下的就是要从[3, 1, 4, 2]
中鲍勃(现在可以看作是先手)的得分减去爱丽丝(现在可以看作是后手)的得分,同理如果移走了最后一个元素,那么剩下的就是[5,3,1,4]
中鲍勃(现在可以看作是先手)的得分减去爱丽丝(现在可以看作是后手)的得分,我们发现我们找到了原问题的一个子问题,我们考虑使用动态规划算法,我们首先可以考虑记忆化搜索
定义dfs(i, j)
, f[i][j]
用来存状态,dfs(i, j)
表示从i
到j
先手和后手的得分差值的最大值,如果先手移除了i
,那么此时得分的差值就是
∑ k = i + 1 k = j s t o n e s [ k ] − d f s ( i + 1 , j ) \sum_{k = i + 1}^{k = j}stones[k] - dfs(i + 1, j) k=i+1∑k=jstones[k]−dfs(i+1,j)
同理得如果移除最后面的石头那么得分的差值就是
∑ k = i k = j − 1 s t o n e s [ k ] − d f s ( i , j − 1 ) \sum_{k = i}^{k = j - 1}stones[k] - dfs(i, j - 1) k=i∑k=j−1stones[k]−dfs(i,j−1)
二者取一个max
即可,一段连续序列的和我们可以使用前缀和算法来处理
记忆化搜索
class Solution {
public:int stoneGameVII(vector<int>& stones) {int n = stones.size();vector<int> sum(n + 1);for (int i = 1; i <= n; i ++) {sum[i] = sum[i - 1] + stones[i - 1];}vector<vector<int>> f(n, vector<int>(n, 0));function<int(int, int)> dfs = [&](int i, int j) -> int {if (i >= j) return 0;int& res = f[i][j]; // 注意这里是引用if (res) return res;res = max(sum[j + 1] - sum[i + 1] - dfs(i + 1, j), sum[j] - sum[i] - dfs(i, j - 1));return res;};return dfs(0, n - 1);}
};
时间复杂度: O ( n 2 ) O(n^2) O(n2)
翻译成递推的形式
dfs(i, j)
就表示 f[i][j]
, 状态转移方程就是f[i][j] = max(sum[j + 1] - sum[i + 1] - f[i + 1][j], sum[j] - sum[i] - f[i][j - 1]);
动态规划(区间dp)
class Solution {
public:int stoneGameVII(vector<int>& stones) {int n = stones.size();vector<int> sum(n + 1);partial_sum(stones.begin(), stones.end(), sum.begin() + 1);vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));for (int len = 2; len <= n; len ++) {for (int i = 0; i + len - 1 < n; i ++) {int l = i, r = i + len - 1;f[l][r] = max(sum[r + 1] - sum[l + 1] - f[l + 1][r], sum[r] - sum[l] - f[l][r - 1]);}}return f[0][n - 1];}
};// 另一个版本
class Solution {
public:int stoneGameVII(vector<int>& stones) {int n = stones.size();vector<int> sum(n + 1);partial_sum(stones.begin(), stones.end(), sum.begin() + 1);vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));for (int i = n - 2; i >= 0; i --) {for (int j = i + 1; j < n; j ++) {f[i][j] = max(sum[j + 1] - sum[i + 1] - f[i + 1][j], sum[j] - sum[i] - f[i][j - 1]);}}return f[0][n - 1];}
};
时间复杂度 O ( n 2 ) O(n^2) O(n2)
partial_sum可以用来求前缀和
结束了
这篇关于LC 1690. 石子游戏 VII的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!