数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中不同帽子互相佩戴的方法数量
假设有n个人和40种不同类型的帽子，这些帽子从1到40编号。现在给出一个名为hats的二维列表，其中hats[i]是第i个人喜欢的所有帽子的列表。我们必须找到n个人互相佩戴不同帽子的方法数量。答案可能非常大，所以返回答案模10^9 + 7。
因此，如果输入类似于[[4,6,2],[4,6]]，则输出为4，因为有4种不同的选择方式，它们是[4,6]，[6,4]，[2,4]，[2,6]。
为了解决这个问题，我们将遵循以下步骤：
m = 10^9 + 7
定义大小为55 x 2^11的二维数组dp
定义一个二维数组v
定义一个函数add()，它将接收a, b，
返回((a mod m) + (b mod m)) mod m
定义一个函数solve()，它将接收idx, mask，
如果mask与req相同，则：
返回1
如果idx与42相同，则：
返回0
如果dp[idx, mask]不等于-1，则：
返回dp[idx, mask]
ret := add(ret, solve(idx + 1, mask))
对于v[idx]中的所有i
如果（将mask右移i位）是偶数，则
ret = add(ret, solve(idx + 1, mask OR 2^i))
dp[idx, mask] := ret
返回ret
从主方法执行以下操作：
用-1初始化dp
n := x的大小
更新v，使其可以包含50个元素
对于初始化i := 0，当i < x的大小时，更新（i增加1），执行：
对于x[i]中的所有j
将i插入v[j]的末尾
req := (2^n) - 1
ret := solve(0, 0)
返回ret
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
int m = 1e9 + 7;
int dp[55][1 << 11];
class Solution {
public:
vector<vector<int> > v;
int req ;
int add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int solve(int idx, int mask){
if (mask == req)
return 1;
if (idx == 42)
return 0;
if (dp[idx][mask] != -1) {
return dp[idx][mask];
}
int ret = add(ret, solve(idx + 1, mask));
for (int i : v[idx]) {
if (!((mask >> i) & 1)) {
ret = add(ret, solve(idx + 1, mask | (1 << i)));
}
}
return dp[idx][mask] = ret;
}
int numberWays(vector<vector<int>>& x){
memset(dp, -1, sizeof dp);
int n = x.size();
v.resize(50);
for (int i = 0; i < x.size(); i++) {
for (int j : x[i]) {
v[j].push_back(i);
}
}
req = (1 << n) - 1;
int ret = solve(0, 0);
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{4,6,2},{4,6}};
cout << (ob.numberWays(v));
}输入
{{4,6,2},{4,6}}输出
4
更新于：2020年6月9日
143 次查看
广告