leetcode1434 每个人戴不同帽子的方案数
思路:
状压dp,哪个维度小就压哪个。
实现:
1 class Solution 2 { 3 public: 4 int numberWays(vectorint>>& hats) 5 { 6 if (hats.empty()) return 0; 7 int n = hats.size(); 8 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 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 };