Tag Archives: 博弈论

LeetCode Can I Win

Leave a reply

LeetCode Can I Win In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100. Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally. You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300. Example 

Input:
maxChoosableInteger = 10
desiredTotal = 11
Output:
false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
又是一道博弈论的题。两个人从1~n中拿数字，问哪个人拿到的数字之和先大于等于desiredTotal。 边界条件是，如果n大于等于desiredTotal，则A开始拿最大数肯定能赢；另一种情况是，如果n个数之和都小于desiredTotal，则无论怎么拿都不可能超过desiredTotal，A不能获胜。 我们用一个长度为n的字符串表示n个数字被拿的状态，’0’表示没被拿，’1’表示被拿了，当然可以用int和位运算来表示，我这里用string是偷懒了。 再用一个hash[string][bool]表示当n个数字的状态为string时A获胜的情况。那么每次A可以从string中为’0’的位置拿数字，如果此时sum + i >= desiredTotal则A肯定获胜；或者sum + i < desiredTotal但是下一轮B没有获胜，即 !win(sum + i, desiredTotal, visited, result)，A也是获胜的。 代码如下： [cpp] class Solution { private: bool win(int sum, int &desiredTotal, string &visited, unordered_map<string,bool>& result) { if (result.find(visited) != result.end())return result[visited]; for (int i = 1; i < visited.size(); ++i) { if (visited[i] == ‘0’) { visited[i] = ‘1’; if (sum + i >= desiredTotal || !win(sum + i, desiredTotal, visited, result)) { visited[i] = ‘0’; //reset result[visited] = true; return true; } visited[i] = ‘0’; //reset } } result[visited] = false; return false; } public: bool canIWin(int maxChoosableInteger, int desiredTotal) { if (maxChoosableInteger >= desiredTotal)return true; int sum = (1 + maxChoosableInteger)*maxChoosableInteger / 2; if (sum < desiredTotal)return false; string visited(maxChoosableInteger + 1, ‘0’); unordered_map<string, bool> result; return win(0, desiredTotal, visited, result); } }; [/cpp] 本代码提交AC，用时309MS。]]>

LeetCode Predict the Winner

Leave a reply

LeetCode Predict the Winner Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins. Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score. Example 1: 

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2: 
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
  1. 1 <= length of the array <= 20.
  2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
  3. If the scores of both players are equal, then player 1 is still the winner.
有关博弈论的题。有两个人A和B，每个人每次能从数组开始或结束位置拿掉一个数，A先拿，谁拿的数字之和越大获胜，问A是否可以获胜。 因为每个人都尽最大的努力想要获胜，所以如果A拿了num[0]，那么B从剩余的nums[1~n-1]拿数字的过程相当于A从nums[0~n-1]拿数字的过程，所以最优化拿数字的过程是一样的。 假设子问题为A从区间nums[s,…,e]拿数字尽量使自己赢，那么如果s==e，只有一个元素，则A拿到的元素和就为这个元素nums[s]。否则A可以尝试拿首元素nums[s]，此时B尽力从nums[s+1,…,e]中拿使B自己赢，所以A的收益就是nums[s]减去B从nums[s+1,…,e]拿到的收益；A也可以拿尾元素nums[e]，此时B尽力从nums[s,…,e-1]中拿使B自己赢，所以A的收益就是nums[e]减去B从nums[s,…,e-1]拿到的收益。A的最大收益就是拿首元素或尾元素获得的收益的较大值，如果大于等于0，说明A可以获胜。 递归代码如下： [cpp] class Solution { private: int helper(vector<int>& nums, int s, int e) { if (s == e)return nums[s]; else return max(nums[s] – helper(nums, s + 1, e), nums[e] – helper(nums, s, e – 1)); } public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); return helper(nums, 0, n – 1) >= 0; } }; [/cpp] 本代码提交AC，用时96MS。 还有一种更清晰的DP方法。假设dp[s][e]为A从区间nums[s,…,e]拿获得的最大收益，如果A拿首元素nums[s]，则获得的收益为nums[s]-dp[s+1][e]，因为B要从剩余的nums[s+1,..,e]拿尽量使自己赢，就相当于A从nums[s+1,…,e]要使自己赢，所以过程都是一样的，dp[s+1][e]就是B的收益。类似的，如果A拿尾元素，则获得的收益为nums[e]-dp[s][e-1]。所以有： $$!dp[s][e]=max(nums[s]-dp[s+1][e],nums[e]-dp[s][e-1])$$ 因为大区间的dp[s][e]会用到较小区间的dp[s+1][e]和dp[s][e-1]，所以可以区间长度进行DP，先求出小区间的值，求大区间时直接用小区间的值就好了。 代码如下： [cpp] class Solution { public: bool PredictTheWinner(vector<int>& nums) { int n = nums.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i)dp[i][i] = nums[i]; // 长度为0 for (int len = 1; len < n; ++len) { for (int s = 0; s + len < n; ++s) { dp[s][s + len] = max(nums[s] – dp[s + 1][s + len], nums[s + len] – dp[s][s + len – 1]); } } return dp[0][n – 1] >= 0; } }; [/cpp] 本代码提交AC，用时3MS。比递归版本快了很多。]]>

LeetCode Nim Game

Leave a reply

292. Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

Example:

Input: 4 Output: false  Explanation: If there are 4 stones in the heap, then you will never win the game;              No matter 1, 2, or 3 stones you remove, the last stone will always be               removed by your friend. 292. Nim Game

博弈论的题。两个人轮流拿石头，一次可以拿1~3个，拿掉最后一个石头的人获胜。规定我先拿，问如果石头数为n时，我是否可以取胜。 看Hint，找规律。

  • 如果n∈[1,3]，则我第一次拿就可以把所有石头拿走，所以我肯定可以获胜。
  • 如果n=4，则无论我第一次拿多少个，因为我最多可以拿3个，所以剩下的石头数转换为了n∈[1,3]的情况，也就是变成了对手肯定能获胜的情况。
  • 如果n∈[5,7]，则我为了获胜，可以想方设法让我第一次拿了之后，剩余4个石头，这样相当于对手遇到n=4的情况，于是转换为我可以获胜的情况。
  • 如果n=8，则无论第一次拿多少个，剩余的石头个数都转换为了n∈[5,7]的情况，也就变成了对手必胜的情况。
  • …

观察以上的分析，发现当n是4的倍数时，我必输；否则我必胜。代码就很好写了：

class Solution {
public:
    bool canWinNim(int n) { return n % 4 != 0; }
};

本代码提交AC，用时0MS。
类似博弈论的题，一定要在纸上写几个例子出来，然后仔细找规律。