Algorithm

Problem Name: 629. K Inverse Pairs Array

For an integer array `nums`, an inverse pair is a pair of integers `[i, j]` where `0 <= i < j < nums.length` and `nums[i] > nums[j]`.

Given two integers n and k, return the number of different arrays consist of numbers from `1` to `n` such that there are exactly `k` inverse pairs. Since the answer can be huge, return it modulo `109 + 7`.

Example 1:

```Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.
```

Example 2:

```Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
```

Constraints:

• `1 <= n <= 1000`
• `0 <= k <= 1000`

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int kInversePairs(int n, int k) {
int[][] dp = new int[n + 1][k + 1];
int mod = 1000000007;
for (int i = 1; i  < = n; i++) {
for (int j = 0; j  < = k; j++) {
if (j == 0) {
dp[i][j] = 1;
} else {
int curr = (dp[i - 1][j] + mod - ((j - i) >= 0 ? dp[i - 1][j - i] : 0)) % mod;
dp[i][j] = (dp[i][j - 1] + curr) % mod;
}
}
}
return ((dp[n][k] + mod - (k > 0 ? dp[n][k - 1] : 0)) % mod);
}
}
``````
Copy The Code &

Input

cmd
n = 3, k = 0

Output

cmd
1

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const kInversePairs = function(n, k) {
const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0))
for (let i = 1; i  <  n + 1; i++) {
dp[i][0] = 1
}
const MOD = 1e9 + 7
for (let i = 1; i  <  n + 1; i++) {
for (let j = 1; j  <  k + 1; j++) {
let val = (dp[i - 1][j] - (j >= i ? dp[i - 1][j - i] : 0) + MOD) % MOD
dp[i][j] = (dp[i][j - 1] + val) % MOD
}
}
return (dp[n][k] - (dp[n][k - 1] || 0) + MOD) % MOD
}
``````
Copy The Code &

Input

cmd
n = 3, k = 0

Output

cmd
1

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def kInversePairs(self, n, k):
dp = [1] + [0] * k
for i in range(2, n + 1):
for j in range(1, k + 1): dp[j] += dp[j - 1]
for j in range(k, 0, -1): dp[j] -= j - i >= 0 and dp[j - i]
return dp[-1] % (10 ** 9 + 7)
``````
Copy The Code &

Input

cmd
n = 3, k = 1

Output

cmd
2