|
1 | 1 | ### 877.Stone-Game |
2 | 2 |
|
3 | | -此题当N为偶数时，先手总是能够胜利。因为先手总是可以选择，他永远拿奇数堆，或者永远拿偶数堆。 |
| 3 | +#### 解法1： |
| 4 | +因为此题的N为偶数，且不会有平局。说明奇数堆的总和，必然与偶数堆的总和不一样。先手玩家可以总是取奇数堆（或者总是取偶数堆），因此可以必胜。 |
4 | 5 |
|
5 | | -比较值得锻炼的是当N为奇数的情况。我们知道肯定是用递归算法，但是该如何设计递归函数呢？比较好的一个选择是 |
| 6 | +#### 解法2： |
| 7 | +当N为奇数时，就没有上述的巧解。对于这种策略型的题目，递归是比较常见的解法。我们设计递归函数```int solve(a,b)```表示先手玩家来当前面对[a,b]区间时可以得到的最大收益。因为这个游戏的得分是此消彼长的关系，所以先手玩家最终取得胜利的条件就是： |
6 | 8 | ``` |
7 | | -int BestWin(arr,a,b) |
| 9 | +solve(1,n) > total - solve(1,n); |
8 | 10 | ``` |
9 | | -表示我是先手来处理[a,b]堆时可以得到的最大值。那么先手取得最后胜利的条件就是： |
10 | | -``` |
11 | | -int sum = accumulate(arr.begin(),a.end(),0); |
12 | | -int MyBest = BestWin(arr,0,N-1); |
13 | | -return MyBest>=sum-MyBest ? 1:2; |
14 | | -``` |
15 | | -对于任意的[a,b]的情况，BestWin(arr,a,b)该如何转移下去呢？不要怕麻烦，逐一讨论： |
16 | | - |
17 | | -1.我选择了a，那么对手可能选a+1，那么我会接下来先手处理 ```BestWin(arr,a+2,b)```; 对手也可能选b，那么我会接下来先手处理 ```BestWin(arr,a+1,b-1)```。那么对手究竟是会选什么呢？他会选择使得我在后期得利更小的那个方案。比如说，如果```BestWin(arr,a+2,b)>BestWin(arr,a+1,b-1)```，那么队手就会选择b。所以，只要我选择了a，那么我的最终得利就是 ```arr[a]+min(BestWin(arr,a+2,b),BestWin(arr,a+1,b-1))```. |
18 | | - |
19 | | -2.同理分析，如果我选择了b，那么对手可能选a+1，也可能选择b-1，最终对手的决策依据是让我接下来的得利最小。所以我的得利会是 ```arr[a] + min(BestWin(arr,a+2,b-1), BestWin(arr,a,b-2))```. |
20 | | - |
21 | | -然后，我在本轮的最终决策是上述两只之间的较大值。 |
22 | | - |
23 | | -此题的递归处理有点绕，保持清晰的思路就能写出简介的代码。 |
| 11 | +那么这个递归函数怎么往下拆解呢？无非就是遵循游戏规则，有两种决策： |
| 12 | +1. 如果我选择了最左边的石头堆（也就是a），那么对手面临也是同一个最优化的问题，只不过范围不同，即```solve(a+1,b)```，对手需要在[a+1,b]这个区间内最大化自己的收益。因此我方在[a,b]区间最终能够得到的收益就是```sum[a:b] - solve(a+1,b)```. |
| 13 | +2. 如果我选择了最右边的石头堆（也就是b），那么对手面临也是同一个最优化的问题，只不过范围不同，即```solve(a,b-1)```，对手需要在[a,b-1]这个区间内最大化自己的收益。因此我方在[a,b]区间最终能够得到的收益就是```sum[a:b] - solve(a,b-1)```. |
24 | 14 |
|
| 15 | +综上，我方必定会在这两个决策中选择一个能够在[a,b]区间收益更多的方案。这就实现了solve(a,b)的递归。无论是我方还是对方，递归的拆解思路总是相同的。递归的边界条件就是a==b时，这堆石头直接拿走。 |
25 | 16 |
|
26 | | -[Leetcode Link](https://leetcode.com/problems/stone-game) |
| 17 | +[Leetcode Link](https://leetcode.com/problems/stone-game) |
0 commit comments