leetcode1434 每个人戴不同帽子的方案数

思路：
状压dp，哪个维度小就压哪个。
实现：
 1 class Solution
 2 {
 3 public:
 4     int numberWays(vector<vector<int>>& hats)
 5     {
 6         if (hats.empty()) return 0;
 7         int n = hats.size();
 8         vector<vector<int>> v(n, vector<int>(41, 0));
 9         for (int i = 0; i < n; i++)
10         {
11             for (int j = 0; j < hats[i].size(); j++)
12             {
13                 v[i][hats[i][j]] = 1;
14             }
15         }
16         vector<vector<int>> dp(41, vector<int>(1 << n, 0));
17         dp[0][0] = 1;
18         int mod = 1e9 + 7;
19         for (int i = 1; i <= 40; i++)
20         {
21             for (int j = 0; j < (1 << n); j++)
22             {
23                 dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
24                 for (int k = 0; k < n; k++)
25                 {
26                     int msk = 1 << k;
27                     if (j & msk and v[k][i])
28                     {
29                         int tmp = j ^ msk;
30                         dp[i][j] = (dp[i][j] + dp[i - 1][tmp]) % mod;
31                     }
32                 }
33             }
34         }
35         return dp[40][(1 << n) - 1];
36     }
37 };