Сложность: hard
Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3, k = 0
Output: 1
👨💻 Алгоритм:
1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.
2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.
3⃣Возвращение результата
Результатом будет значение dp[n][k].
😎 Решение:
func kInversePairs(_ n: Int, _ k: Int) -> Int {
let MOD = 1_000_000_007
var dp = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1)
dp[0][0] = 1
for i in 1...n {
dp[i][0] = 1
for j in 1...k {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD
if j >= i {
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD
}
}
}
return dp[n][k]
}Ставь 👍 и забирай 📚 Базу знаний