Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: 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 {
    private $memo;
    private $done;
    private $n;
    private $MOD = 1000000007;
    private $hatsToPeople;

    function numberWays($hats) {
        $this->n = count($hats);
        $this->hatsToPeople = [];

        foreach ($hats as $i => $personHats) {
            foreach ($personHats as $hat) {
                if (!isset($this->hatsToPeople[$hat])) {
                    $this->hatsToPeople[$hat] = [];
                }
                $this->hatsToPeople[$hat][] = $i;
            }
        }

        $this->done = pow(2, $this->n) - 1;
        $this->memo = array_fill(0, 41, array_fill(0, $this->done, -1));

        return $this->dp(1, 0);
    }

    private function dp($hat, $mask) {
        if ($mask == $this->done) {
            return 1;
        }

        if ($hat > 40) {
            return 0;
        }

        if ($this->memo[$hat][$mask] != -1) {
            return $this->memo[$hat][$mask];
        }

        $ans = $this->dp($hat + 1, $mask);

        if (isset($this->hatsToPeople[$hat])) {
            foreach ($this->hatsToPeople[$hat] as $person) {
                if (($mask & (1 << $person)) == 0) {
                    $ans = ($ans + $this->dp($hat + 1, $mask | (1 << $person))) % $this->MOD;
                }
            }
        }

        $this->memo[$hat][$mask] = $ans;
        return $ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний