Сложность: medium
В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число 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.
😎 Решение:
public class Solution {
public int countDerangements(int n) {
final int MOD = 1000000007;
if (n == 0) return 1;
if (n == 1) return 0;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = (int)((long)(i - 1) * (dp[i - 1] + dp[i - 2]) % MOD);
}
return dp[n];
}
}Ставь 👍 и забирай 📚 Базу знаний