在leetcode中，經(jīng)常會(huì)遇到判斷兩人游戲，一方是輸還是贏的問(wèn)題。有g(shù)uess number higher or lower, can I win,PRedict the winner等。這類(lèi)問(wèn)題都假設(shè)雙方在最優(yōu)策略下，甲方是否會(huì)贏。 這類(lèi)問(wèn)題都可以用動(dòng)態(tài)規(guī)劃來(lái)解決，關(guān)鍵在于采用top-down的備忘錄策略，每解決一個(gè)小的子問(wèn)題，都把相應(yīng)的結(jié)果記錄在備忘錄上，下次遇到相同的問(wèn)題時(shí)，直接查詢即可。這樣可以把原來(lái)O(n!)的復(fù)雜度降低到O(2^n)的復(fù)雜度。 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表記錄每種可能的選擇所對(duì)應(yīng)的結(jié)果，這里map
class Solution { map<int,bool> m;//用來(lái)記錄子問(wèn)題的備忘錄 bool helper(int desiredTotal, int used,int n) { if(m.count(used)!=0) return m[used];//如果m中已經(jīng)有結(jié)果，直接輸出。 int bit=1; if(desiredTotal<=0)//說(shuō)明上次，即對(duì)方已經(jīng)達(dá)到想要的和，輸 { m[used]=0; return 0; } for(int i=0;i<n;i++,bit<<=1) { if((used&bit)==0)//該i未被用 { if(i>=desiredTotal)//能達(dá)到和 { m[used]=1; return true; } used|=bit; bool nextwinner=helper(desiredTotal-i-1,used,n);//對(duì)方的輸贏 used-=bit; if(!nextwinner)//對(duì)方輸 { 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. 也是雙方游戲,最后和大的獲勝.如果一方選擇了兩端的任意一個(gè)數(shù)，可以看成加，而另一方選擇它的數(shù)對(duì)于自己來(lái)說(shuō)可以看成是減。只要最后的結(jié)果不小于0，說(shuō)明自己就比對(duì)手高。這里也用一個(gè)存儲(chǔ)記錄表來(lái)記錄當(dāng)前子問(wèn)題的結(jié)果。對(duì)于子數(shù)組中的該問(wèn)題，dp[s][e] 表示對(duì)于在數(shù)組nums[s,…,e]中問(wèn)題的解。
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]; }};這里涉及到的雙方對(duì)弈的游戲，都假設(shè)對(duì)手所作的決策也是最優(yōu)的，即minimax算法。但是，運(yùn)用備忘錄的DP算法，而不是遞歸，可以大大加快速度。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
