leetcode 464.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.      

想法：

現在已經條件反射了，看見這種第一眼連暴力求解思路都沒有的題，不是動态規劃就是貪心算法。

好嘛，貪心：每次拿最大的數字然後。。。你以為這倆player都是白癡嗎。

假如數字集合1-10，A為了赢，拿10,B拿9，好吧，輸了吧？

是以顯然是動态規劃。

動态規劃我們一般用一個狀态來表示，一個數組來儲存之前可能用到的狀态。

這裡第一次我犯了個錯誤，沒有考慮數字“是否被使用了”這個關鍵要點。是以以為一維數組就可以解決。

是以，錯的慘兮兮。。。

之後我想，這玩意是不是就像走迷宮似的，為了嘗試所有可能，要利用回溯？

ps：就是一種試錯法，一旦發現不符合要求，那麼利用遞歸後的語句來把之前修改的值重新修改為原來的值。

但是我依然沒有想到怎麼利用這個來解題。

萬般無奈下，看了答案。原來把這個“被使用過的數字集合”也看做狀态啊。。。

下面是python版答案（已經通過）：

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if desiredTotal<=0:
            return True
        if (1+maxChoosableInteger)*maxChoosableInteger//2<desiredTotal:
            return False
        state=['0' for x in range(maxChoosableInteger)]
        d={}
        def dfs(total,state,d):
            s=''.join(state)
            if d.get(s,None):
                return d[s]
            for i in range(len(state)):
                if state[i]=='0':
                    state[i]='1'
                    if total<=i+1 or dfs(total-i-1,state,d)==False:# 遞歸處
                        d[s]=True
                        state[i]='0'
                        return True
                    state[i]='0'
            d[s]=False
            return False
        return dfs(desiredTotal,state,d)
           

這題不可謂不精妙。

逐行說一說。

第一個if語句，如果目标值都小于等于0了，那你A随便拿一個數字都赢了 啊，還算好了解。

第二個if說的就是我在貪心算法中說到的那個情況，一直取最大，你都達不到目标值，還是拉倒吧，輸了。

state是數字集合狀态，我說說為什麼用字元集來表示，首先你要能修改這個狀态友善回溯，然後為了利用“緩存”，實際上就是dp裡的帶記憶的數組（這裡是一個字典），我們需要讓它是hashable（可哈希的），這樣我考慮了一下，python中不能像java一樣修改字元時建立對象，是以用join函數生成的不可變字元串來成鍵值。

然後就是一個深度優先搜尋。最關鍵的地方當然是帶标記的那個“遞歸處”，連上for循環實際上是一個檢查性遞歸，遞歸函數dfs的含義實際上是吧題目的意思反向來解答：把這個數字減掉的目标值是否能用剩餘的數字子集來加到。

字典d相當于緩存，如果這個狀态已經被儲存了，那就是說：這個狀态，能/不能完成給定函數的目标值。

最終狀态儲存，并且傳回修改。

感想：

本質上就是一個二狀态的dp，隻不過其中一個狀态以字典實作，另一個用dfs求解。

第一次遇到這種二狀态的dp，存一下。