LC 1655. 分配重复整数

https://leetcode-cn.com/problems/distribute-repeating-integers/

这是典型的装箱问题，但是我忘记了动态规划的算法。写了一个粗糙的记忆化搜索，过了但是时间很长。

看了题解，想起来要用动态规划。 `dp[i][st]` 表示前面i个订单是否可以满足用st表示的顾客子集。另外学到一个奇怪的知识，就是这个算法时间复杂度是O(n*3^m).

至于这个3^m是怎么来的，可以这么考虑内部循环：

  1. st中有k个元素的个数是C(m, k)
  2. k的范围是 `0..m`.

所以内循环次数是 `C(m,k)*2^k. k=0..m`, 这个式子的结果是3^m. 

class Solution2:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        from collections import Counter
        cnt = Counter(nums)
        values = list(cnt.values())
        values.sort()
        quantity.sort()

        values = [x for x in values if x >= quantity[0]]
        if not values:
            return False
        if values[-1] < quantity[-1]:
            return False
        n, m = len(values), len(quantity)

        SUM = [0] * (1 << m)
        for i in range(1 << m):
            acc = 0
            for j in range(m):
                if (i >> j) & 0x1:
                    acc += quantity[j]
            SUM[i] = acc

        DP = [[0] * (1 << m) for _ in range(n + 1)]
        DP[0][0] = 1
        for i in range(n):
            for j in range(1 << m):
                st = j
                ok = 0
                if DP[i][j]:
                    DP[i + 1][j] = 1
                    continue

                while st > 0:
                    if SUM[st] <= values[i] and DP[i][j - st]:
                        ok = 1
                        break
                    st = (st - 1) & j
                DP[i + 1][j] = ok
        ans = DP[n][-1]
        return bool(ans)