0%

leetcode石子游戏专题 van♂游戏

leetcode 877 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。

亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。

1
2
3
4
5
6
7
8
9
10
示例:

输入:[5,3,4,5]
输出:true
解释:
亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗,这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。
这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true

思路:典型的区间dp,根据区间长度划分状态,f[i][j]表示取完了除i-j区间之后玩家可得最高分数,如果当前轮到A那么应当在取区间首尾中的最大值,否则只能得到首尾中的最小值。当前轮到谁可以这样确定,因为每轮只能取一次,所以每次剩下的石堆数量要么是奇数,要么是偶数,所以可以根据这个特性来判断是谁取数。
有动态转移方程:轮到自己时$dp[i][j]=max(dp[i+1][j]+nums[i],dp[i][j-1]+nums[j]);$
轮到对方时,$dp[i][j]=min(dp[i+1][j],dp[i][j-1];$
最后判断先手玩家得分是否大于另一个玩家。
时间复杂度: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool stoneGame(vector<int>& nums) {
int n = nums.size();
vector<vector<int>>f(n,vector<int>(n,0));
if(n & 1)for(int i=0;i<n;i++)f[i][i] = nums[i];

for(int i = 2 ; i<=n; i++){//枚举区间长度
for(int j = 0;j+i-1<n;j++){//f[i][j]表示取完了除i-j区间之后 玩家可得最高分数
int l = j, r = i+j-1;
if((n-(r-l+1))%2==0)f[l][r] = max(f[l+1][r] + nums[l],f[l][r-1]+nums[r]);
else f[l][r] = min(f[l+1][r],f[l][r-1]);
}
}
int sum = 0;
for(auto i=0;i<n;i++)sum+=nums[i];
if(f[0][n-1]>=sum-f[0][n-1])return true;
else return false;
}
};

leetcode 1140 石子游戏 II

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行,亚历克斯先开始。最初,M = 1。

在每个玩家的回合中,该玩家可以拿走剩下的 前 X 堆的所有石子,其中 1 <= X <= 2M。然后,令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平,返回亚历克斯可以得到的最大数量的石头。

1
2
3
4
5
6
7
8
示例:

输入:piles = [2,7,9,4,4]
输出:10
解释:
如果亚历克斯在开始时拿走一堆石子,李拿走两堆,接着亚历克斯也拿走两堆。在这种情况下,亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
如果亚历克斯在开始时拿走两堆石子,那么李就可以拿走剩下全部三堆石子。在这种情况下,亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10

思路:只能理解记忆化搜索的思路,没理解dp的思路。memo[i][j]表示从下标i开始取数时,取x(1<=x<=j)堆石子能得到的最多的石子数。所以显然可以记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int presum[101];
unordered_map<int,unordered_map<int,int>>memo;
int n;
int stoneGameII(vector<int>& piles) {
n = piles.size();
for(int i=1;i<=n;i++)presum[i]=presum[i-1]+piles[i-1];
return dfs(piles,0,1);
}
int dfs( vector<int>& piles,int start,int m){
if(memo.find(start)!=memo.end() && memo[start].find(m)!=memo[start].end())return memo[start][m];
if(start>=n)return 0;
int max_stone=0;
for(int i=1;i<=2*m;i++){
int nm = max(i,m);
int next_max=dfs(piles,start+i,nm);//对方取得的最大石子数
//利用前缀和更新自己能获得的最大石子数
max_stone = max(max_stone,presum[n] - presum[start]-next_max);
}
memo[start][m]=max_stone;
return max_stone;
}
};

leetcode 1406 石子游戏 III

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ,Bob 赢了就返回 “Bob”,平局(分数相同)返回 “Tie” 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
示例 1

输入:values = [1,2,3,7]
输出:"Bob"
解释:Alice 总是会输,她的最佳选择是拿走前三堆,得分变成 6 。但是 Bob 的得分为 7,Bob 获胜。
示例 2

输入:values = [1,2,3,-9]
输出:"Alice"
解释:Alice 要想获胜就必须在第一个回合拿走前三堆石子,给 Bob 留下负分。
如果 Alice 只拿走第一堆,那么她的得分为 1,接下来 Bob 拿走第二、三堆,得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆,输掉比赛。
如果 Alice 拿走前两堆,那么她的得分为 3,接下来 Bob 拿走第三堆,得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆,同样会输掉比赛。
注意,他们都应该采取 最优策略 ,所以在这里 Alice 将选择能够使她获胜的方案。
示例 3

输入:values = [1,2,3,6]
输出:"Tie"
解释:Alice 无法赢得比赛。如果她决定选择前三堆,她可以以平局结束比赛,否则她就会输。
示例 4

输入:values = [1,2,3,-1,-2,-3,7]
输出:"Alice"
示例 5

输入:values = [-1,-2,-3]
输出:"Tie"

思路:f[i]表示从下标i开始取数,先手比后手多的分数。

  1. 初始值,f(n)=0,其余待定。
  2. 转移时,对于 f(i) 有三种决策,取第 i 堆,取第 i 和 i+1 堆,以及取第 i,i+1 和 i+2 堆,对应的转移分别为 $max(s(i)−f(i+1),s(i)+s(i+1)−f(i+2),s(i)+s(i+1)+s(i+2)−f(i+3)$。
  3. 最终,如果 f(0)=0,则平局;如果 f(0)>0 则 Alice 胜,否则 Bob 胜。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
    string stoneGameIII(vector<int>& stoneValue) {
    int n = stoneValue.size();
    vector<int> f(n + 1);

    f[n] = 0;

    for (int i = n - 1; i >= 0; i--) {
    f[i] = stoneValue[i] - f[i + 1];
    if (i < n - 1)
    f[i] = max(f[i], stoneValue[i] + stoneValue[i + 1] - f[i + 2]);

    if (i < n - 2)
    f[i] = max(f[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2]
    - f[i + 3]);
    }

    if (f[0] == 0)
    return "Tie";
    else if (f[0] > 0)
    return "Alice";
    else return "Bob";
    }
    };