讨论/题目交流/🐱 第 25 场夜喵双周赛/
🐱 第 25 场夜喵双周赛
展开讨论
力扣 (LeetCode)发起于 2020-05-02

有大佬能看看 T4 为什么超时吗
这个复杂度应该怎么分析..

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        n = len(hats)
        dp = [dict() for _ in range(n)]
        for idx, hat in enumerate(hats):
            if idx == 0:
                for h in hat:
                    dp[idx][1 << h] = 1
                continue
            for key in dp[idx - 1]:
                for h in hat:
                    if (1 << h) & (key) == 0:
                        cur = (1 << h) + key
                        if cur not in dp[idx]:
                            dp[idx][cur] = dp[idx - 1][key]
                        else:
                            dp[idx][cur] += dp[idx - 1][key]
                            dp[idx][cur] %= MOD
        return sum(dp[-1].values()) % MOD
展开全部 29 讨论