#ЛитКод
Задача: 634. Find the Derangement of An Array

В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3
Output: 2

👨‍💻 Алгоритм:

1⃣Инициализация массива для хранения результатов
Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0.

2⃣Вычисление количества отклонений
Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD.

3⃣Возвращение результата
Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7.

😎 Решение:

class Solution {
    fun countDerangements(n: Int): Int {
        val MOD = 1_000_000_007
        if (n == 0) return 1
        if (n == 1) return 0
        val dp = IntArray(n + 1)
        dp[0] = 1
        dp[1] = 0
        for (i in 2..n) {
            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2].toLong()) % MOD).toInt()
        }
        return dp[n]
    }
}

👉Новости 👉Платформа