Сложность: hard
Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.
Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.
Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.
Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.
Пример:
Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions.
First person choose hat 3, Second person choose hat 4 and last one hat 5.
👨💻 Алгоритм:
1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.
2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.
3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.
😎 Решение:
class Solution {
var memo: [[Int]] = []
var done: Int = 0
var n: Int = 0
let MOD = 1000000007
var hatsToPeople: [Int: [Int]] = [:]
func numberWays(_ hats: [[Int]]) -> Int {
n = hats.count
for (i, hatList) in hats.enumerated() {
for hat in hatList {
hatsToPeople[hat, default: []].append(i)
}
}
done = (1 << n) - 1
memo = Array(repeating: Array(repeating: -1, count: done), count: 41)
return dp(1, 0)
}
private func dp(_ hat: Int, _ mask: Int) -> Int {
if mask == done { return 1 }
if hat > 40 { return 0 }
if memo[hat][mask] != -1 { return memo[hat][mask] }
var ans = dp(hat + 1, mask)
if let people = hatsToPeople[hat] {
for person in people {
if (mask & (1 << person)) == 0 {
ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD
}
}
}
memo[hat][mask] = ans
return ans
}
}Ставь 👍 и забирай 📚 Базу знаний