629. K Inverse Pairs Array

leetcode hard

#array#csharp#dynamic-programming#hard#leetcode

Task

Для целочисленного массива 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

C# solution

matched/original

public class Solution {
    public int KInversePairs(int n, int k) {
        int MOD = 1000000007;
        int[,] dp = new int[n + 1, k + 1];
        dp[0, 0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i, 0] = 1;
            for (int 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];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int KInversePairs(int n, int k) {
        int MOD = 1000000007;
        int[,] dp = new int[n + 1, k + 1];
        dp[0, 0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i, 0] = 1;
            for (int 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];
    }
}

Java solution

matched/original

public class Solution {
    public int kInversePairs(int n, int k) {
        int MOD = 1000000007;
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                if (j >= i) {
                    dp[i][j] -= dp[i - 1][j - i];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }

        return dp[n][k];
    }
}

JavaScript solution

matched/original

var kInversePairs = function(n, k) {
    const MOD = 1e9 + 7;
    const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= n; i++) {
        dp[i][0] = 1;
        for (let j = 1; j <= k; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            if (j >= i) {
                dp[i][j] -= dp[i - 1][j - i];
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD;
        }
    }

    return dp[n][k];
};

Python solution

matched/original

def kInversePairs(n, k):
    MOD = 10**9 + 7
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    
    for i in range(1, n + 1):
        dp[i][0] = 1
        for j in range(1, k + 1):
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
            if j >= i:
                dp[i][j] -= dp[i - 1][j - i]
            dp[i][j] %= MOD
    
    return dp[n][k]

Go solution

matched/original

package main

const MOD = 1000000007

func kInversePairs(n int, k int) int {
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, k+1)
    }
    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]
}

Explanation

Algorithm

Инициализация

Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

Заполнение DP-таблицы

Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

Возвращение результата

Результатом будет значение dp[n][k].

😎