資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告