Sponsored
Sponsored
We use a two-dimensional dynamic programming array, where dp[i][j] represents the number of permutations of array {1, 2, ..., i} with exactly j inverse pairs. The transition is based on the idea that when we insert a new element into an existing permutation, it can create new inverse pairs from 0 up to i-1.
Time Complexity: O(n*k)
Space Complexity: O(n*k)
1public class KInversePairs {
2 public int kInversePairs(int n, int k) {
3 final int MOD = 1000000007;
4 int[][] dp = new int[n + 1][k + 1];
5 for (int i = 0; i <= n; i++) {
6 dp[i][0] = 1;
7 for (int j = 1; j <= k; j++) {
8 if (i > 0) {
9 dp[i][j] = (dp[i-1][j] + MOD - (j >= i ? dp[i-1][j-i] : 0)) % MOD;
10 }
11 dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
12 }
13 }
14 return (dp[n][k] + MOD - (k > 0 ? dp[n][k-1] : 0)) % MOD;
15 }
16 public static void main(String[] args) {
17 int n = 3, k = 1;
18 KInversePairs kip = new KInversePairs();
19 System.out.println(kip.kInversePairs(n, k));
20 }
21}The Java solution follows the same logic but uses arrays and loops as per Java syntax. The logic involves managing previous results and current computations using the DP table, while handling large numbers with modulo.