在leetcode中，經常會遇到判斷兩人游戲，一方是輸還是贏的問題。有guess number higher or lower, can I win,PRedict the winner等。這類問題都假設雙方在最優策略下，甲方是否會贏。 這類問題都可以用動態規劃來解決，關鍵在于采用top-down的備忘錄策略，每解決一個小的子問題，都把相應的結果記錄在備忘錄上，下次遇到相同的問題時，直接查詢即可。這樣可以把原來O(n!)的復雜度降低到O(2^n)的復雜度。 1) 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. 思路：用hash表記錄每種可能的選擇所對應的結果，這里map
class Solution { map<int,bool> m;//用來記錄子問題的備忘錄 bool helper(int desiredTotal, int used,int n) { if(m.count(used)!=0) return m[used];//如果m中已經有結果，直接輸出。 int bit=1; if(desiredTotal<=0)//說明上次，即對方已經達到想要的和，輸 { m[used]=0; return 0; } for(int i=0;i<n;i++,bit<<=1) { if((used&bit)==0)//該i未被用 { if(i>=desiredTotal)//能達到和 { m[used]=1; return true; } used|=bit; bool nextwinner=helper(desiredTotal-i-1,used,n);//對方的輸贏 used-=bit; if(!nextwinner)//對方輸 { m[used]=1; return true; } } } m[used]=0; return 0; } public: bool canIWin(int maxChoosableInteger, int desiredTotal) { int n=maxChoosableInteger; int sum=(1+maxChoosableInteger)*maxChoosableInteger/2; if(sum<desiredTotal) return false; if(maxChoosableInteger>=desiredTotal) return true; if(desiredTotal==0) return 1; return helper(desiredTotal,0,n); }};2) 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 <= length of the array <= 20. Any scores in the given array are non-negative integers and will not exceed 10,000,000. If the scores of both players are equal, then player 1 is still the winner. 也是雙方游戲,最后和大的獲勝.如果一方選擇了兩端的任意一個數，可以看成加，而另一方選擇它的數對于自己來說可以看成是減。只要最后的結果不小于0，說明自己就比對手高。這里也用一個存儲記錄表來記錄當前子問題的結果。對于子數組中的該問題，dp[s][e] 表示對于在數組nums[s,…,e]中問題的解。
class Solution {public: bool PredictTheWinner(vector<int>& nums) { int i,n=nums.size(); vector<vector<int>> dp(n,vector<int>(n,0));//備忘錄 int res=DP(dp,0,n-1,nums); return res>=0; } int DP(vector<vector<int>> &dp, int s, int e,vector<int>& nums) { if(s==e) return nums[s]; if(dp[s][e]!=0) return dp[s][e]; int tmp=max(nums[s]-DP(dp,s+1,e,nums),nums[e]-DP(dp,s,e-1,nums)); dp[s][e]=tmp; return dp[s][e]; }};這里涉及到的雙方對弈的游戲，都假設對手所作的決策也是最優的，即minimax算法。但是，運用備忘錄的DP算法，而不是遞歸，可以大大加快速度。
新聞熱點
疑難解答
