Formatted question description: https://leetcode.ca/all/629.html

# 629. K Inverse Pairs Array (Hard)

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.

We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.

Since the answer may be very large, the answer should be 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 pair.


Example 2:

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


Note:

1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

Companies:
Works Applications

Related Topics:
Dynamic Programming

## Solution 1.

Denote R(n, k) as the result number, P as a permutation.

For n = 1, only 1 case for k = 0. So R(1, 0) = 1.

| 1 |               // If P = 1


For n = 2:

| 1 |               // If P = 1
| 1 |           // If P = 2
|
V
| 1 | 1 |


For n = 3:

| 1 | 1 |               // If P = 1
| 1 | 1 |           // If P = 2
| 1 | 1 |       // If P = 3
|
V
| 1 | 2 | 2 | 1 |



For n = 4:

| 1 | 2 | 2 | 1 |              // If P = 1
| 1 | 2 | 2 | 1 |          // If P = 2
| 1 | 2 | 2 | 1 |      // If P = 3
| 1 | 2 | 2 | 1 |  // If P = 4
|
V
| 1 | 3 | 5 | 6 | 5 | 3 | 1 |


// OJ: https://leetcode.com/problems/k-inverse-pairs-array/

// Time: O(N * K^2)
// Space: O(K)
class Solution {
public:
int kInversePairs(int n, int k) {
if (k > n * (n - 1) / 2) return 0;
int mod = 1e9 + 7;
vector<int> prev(1, 1);
for (int i = 1; i <= n; ++i) {
vector<int> cnt(min(k + 1, (int)prev.size() + i - 1));
for (int j = 0; j < i; ++j) {
for (int t = 0; t < prev.size(); ++t) {
if (j + t > k) break;
cnt[j + t] = (cnt[j + t] + prev[t]) % mod;
}
}
prev = cnt;
}
return prev[k];
}
};


## Solution 2. DP

Denote F(N, K) as the result.

Observations:

• Valid range of K is [0, N * (N - 1) / 2]. F(N, K) = 0 if K[0, N * (N - 1) / 2].
• F(N, 0) = F(N, N * (N - 1) / 2) = 1.

For F(N, K), let’s pick 1, 2, …, N as the first number:

• When 1 is picked, we need to compute F(N - 1, K).
• When 2 is picked, we need to compute F(N - 1, K - 1).
• When N is picked, we need to compute F(N - 1, K - (N - 1)).

Eventually F(N, K) = Sum(F(N - 1, K) + F(N - 1, K - 1) + ... + F(N - 1, K - (N - 1)).

We can use this formula to compute F(n, K) for N = 1, 2, 3, ..., N.

// OJ: https://leetcode.com/problems/k-inverse-pairs-array/

// Time: O(NK * min(N, K))
// Space: O(K)
class Solution {
public:
int kInversePairs(int N, int K) {
if (K > N * (N - 1) / 2) return 0;
vector<int> m(K + 1, 0);
m = 1;
int mod = 1e9 + 7;
for (int n = 2; n <= N; ++n) {
for (int k = min(K, (n * (n - 1) / 2)); k > 0; --k) {
for (int i = max(0, k - n + 1); i < k && m[i]; ++i) {
m[k] = (m[k] + m[i]) % mod;
}
}
}
return m[K];
}
};


## Solution 3. DP + Cumulative Sum

In Solution 2, we alway compute the sum of a segment of the previous row. Considering this, we can use Cumulative Sum to make it faster.

Denote G(N, K) as Sum{k=[0,K]}(F(N, k)).

G(N, K) = G(N, K - 1) + F(N, K)
= G(N, K - 1) + [F(N - 1, K - min(K, N - 1)) + ... + F(N - 1, K)]
= G(N, K - 1) + [G(N - 1, K) - G(N - 1, K - min(K, N - 1) - 1)]


After all the G(N, K) are computed, we can get F(N, K) = G(N, K) - G(N, K - 1).

// OJ: https://leetcode.com/problems/k-inverse-pairs-array/

// Time: O(NK)
// Space: O(K)
class Solution {
public:
int kInversePairs(int N, int K) {
if (K > N * (N - 1) / 2) return 0;
vector<vector<int>> dp(2, vector<int>(K + 1, 0));
dp = dp = 1;
int mod = 1e9 + 7;
for (int n = 2; n <= N; ++n) {
int bound = min(K, n * (n - 1) / 2);
for (int k = 1; k <= bound; ++k) {
dp[n % 2][k] = (dp[n % 2][k - 1] + (mod + dp[(n - 1) % 2][k] - dp[(n - 1) % 2][k - min(k, n - 1) - 1]) % mod) % mod;
}
}
return dp[N % 2][K];
}
};


Java

class Solution {
public int kInversePairs(int n, int k) {
final int MODULO = 1000000007;
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++)
dp[i] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int sum = (dp[i - 1][j] + dp[i][j - 1]) % MODULO;
dp[i][j] = (sum - ((j - i < 0) ? 0 : dp[i - 1][j - i]) + MODULO) % MODULO;
}
}
return dp[n][k];
}
}