leetcode 877 石子游戏
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。
亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。
1 | 示例: |
$2 <= piles.length <= 500$
$piles.length 是偶数。$
$1 <= piles[i] <= 500$
$sum(piles) 是奇数。$
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons
思路:典型的区间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 | class Solution { |
leetcode 1140 石子游戏 II
亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行,每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
亚历克斯和李轮流进行,亚历克斯先开始。最初,M = 1。
在每个玩家的回合中,该玩家可以拿走剩下的 前 X 堆的所有石子,其中 1 <= X <= 2M。然后,令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设亚历克斯和李都发挥出最佳水平,返回亚历克斯可以得到的最大数量的石头。
1 | 示例: |
$1 <= piles.length <= 100$
$1 <= piles[i] <= 10 ^ 4$
来源:力扣(LeetCode)
思路:只能理解记忆化搜索的思路,没理解dp的思路。memo[i][j]表示从下标i开始取数时,取x(1<=x<=j)堆石子能得到的最多的石子数。所以显然可以记忆化搜索。
1 | class Solution { |
leetcode 1406 石子游戏 III
Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。
Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。
假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ,Bob 赢了就返回 “Bob”,平局(分数相同)返回 “Tie” 。
1 | 示例 1: |
$1 <= values.length <= 50000$
$-1000 <= values[i] <= 1000$
来源:力扣(LeetCode)
思路:f[i]表示从下标i开始取数,先手比后手多的分数。
- 初始值,f(n)=0,其余待定。
- 转移时,对于 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)$。
- 最终,如果 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
25class 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";
}
};