Сложность: 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:
def numberWays(self, hats: List[List[int]]) -> int:
MOD = 1000000007
n = len(hats)
hatsToPeople = {}
for i, hatList in enumerate(hats):
for hat in hatList:
if hat not in hatsToPeople:
hatsToPeople[hat] = []
hatsToPeople[hat].append(i)
done = (1 << n) - 1
memo = [[-1] * done for _ in range(41)]
def dp(hat, mask):
if mask == done:
return 1
if hat > 40:
return 0
if memo[hat][mask] != -1:
return memo[hat][mask]
ans = dp(hat + 1, mask)
if hat in hatsToPeople:
for person in hatsToPeople[hat]:
if (mask & (1 << person)) == 0:
ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD
memo[hat][mask] = ans
return ans
return dp(1, 0)
Ставь 👍 и забирай 📚 Базу знаний