Задача: 629. K Inverse Pairs Array
Сложность: 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].

😎 Решение:

function kInversePairs($n, $k) {
    $MOD = 1000000007;
    $dp = array_fill(0, $n + 1, array_fill(0, $k + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        $dp[$i][0] = 1;
        for ($j = 1; $j <= $k; $j++) {
            $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];
}

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