2020年5月3日 星期日

Leetcode題解 Python：Number of Ways to Wear Different Hats to Each Other

給一組二維串列，一維代表第 i 位的人，二維代表該位置上的人可選的帽子種類編號。回傳全部人都戴上帽子且都是不同種類的方法數。

這題是DP，最大的特徵就是數目很大，需要取餘。(以前提過)

但DP的精華就是如何設計DP在放些什麼，而我這次學到了「bit」的方法。(然而我沒有在contest解出來QQ)

由於帽子種類跟人數都是有限制範圍的，若要取DP，可以由帽子做分配，或是由人開始。

要選哪一個？這我當時沒有想清楚，結果用人為主體。然後backtrace都超時。

以人為主體的話：1人可能有40種﹐最多有10人，是 40**10 是嗎？不，最糟是40*39*38*...*30。

以帽子為主體的話：則是 40*10! ，40是帽子的種類，10的階乘是代表沒有戴上帽子的人。只要能提前戴上帽子，就可以提前結束遞迴函數。


而且我之前沒有想到bit法，用 set 是不能當 hashtable 的 key ， 於是我用 tuple，太花時間。

bit法是相互獨立且非 1即 0 的狀態才適用，剛好這題適用，不論是用來表示帽子被選擇，或是誰戴上帽子，都可以。

我以為會有很多種的方法，結果沒有，而目前沒有看到更好的解法，大概都這一套。

Python 
from functools import lru_cache
from collections import defaultdict

class Solution:    
    def numberWays(self, hats) -> int:      
        n = 40 # 題目限制的帽子種類
        m = (1 << len(hats)) - 1 # 全部人都戴上帽子的狀態
        
        hatToP = defaultdict(list)
        for i, each in enumerate(hats):
            for hat in each:
                hatToP[hat].append(i)   
 
        @lru_cache(None) 
        def search(i, state):  
            if state == m: return 1 
            if i > n: return 0              
            ways = 0            
            for p in hatToP[i]:
                if state < (state | 1 << p): # 選
                    ways += search(i+1, (state | 1 << p))  
            ways += search(i+1, state) # 不選   
            return ways % (10**9+7)
        
        return search(0, 0)
於
標籤： ,