题目描述
1434. 每个人戴不同帽子的方案数
解法：状态压缩DP（C++）
详细参考 lucifer1004的解
针对代码解释一下，状态转移方程表述的是后面的状态由前面的状态决定，而我们编码的时候是先处理前面的状态，再慢慢推到后面的状态
class Solution {
public:int numberWays(vector<vector<int>>& hats) {
const long long MOD = 1e9+7;int n = hats.size();vector<long long> dp(1<<n);vector<set<int>> s(41);dp[0] = 1;for(int i=0;i<n;i++)for(int hat: hats[i])s[hat].insert(i);for(int i=1;i<=40;i++){
vector<long long> ndp(dp);for(int state=(1<<n)-1;state>=0;state--){
for(int person: s[i]){
if(state&(1<<person)) continue;int nxt = state+(1<<person);ndp[nxt] += dp[state];ndp[nxt] %= MOD;}}swap(dp, ndp);}return dp[(1<<n)-1];}
};