# Java DP O(nk) solution

• dp[n][k] denotes the number of arrays that have k inverse pairs for array composed of 1 to n
we can establish the recursive relationship between dp[n][k] and dp[n-1][i]:

if we put n as the last number then all the k inverse pair should come from the first n-1 numbers
if we put n as the second last number then there's 1 inverse pair involves n so the rest k-1 comes from the first n-1 numbers
...
if we put n as the first number then there's n-1 inverse pairs involve n so the rest k-(n-1) comes from the first n-1 numbers

`dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]`

It's possible that some where in the right hand side the second array index become negative, since we cannot generate negative inverse pairs we just treat them as 0, but still leave the item there as a place holder.

`dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]`
`dp[n][k+1] = dp[n-1][k+1]+dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1] `

so by deducting the first line from the second line, we have

`dp[n][k+1] = dp[n][k]+dp[n-1][k+1]-dp[n-1][k+1-n]`

Below is the java code:

``````    public static int kInversePairs(int n, int k) {
int mod = 1000000007;
if (k > n*(n-1)/2 || k < 0) return 0;
if (k == 0 || k == n*(n-1)/2) return 1;
long[][] dp = new long[n+1][k+1];
dp[2][0] = 1;
dp[2][1] = 1;
for (int i = 3; i <= n; i++) {
dp[i][0] = 1;
for (int j = 1; j <= Math.min(k, i*(i-1)/2); 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 (int) dp[n][k];
}``````

• @dreamchase
Could you explain to me what this line is doing `dp[i][j] = (dp[i][j]+mod) % mod;`
Why only the line `dp[i][j] = (dp[i][j]) % mod;` doesn't work?

• @johirbuet
the previous line `if (j >= i) dp[i][j] -= dp[i-1][j-i];` might result in a negative value, because dp[i][j] and dp[i-1][j-i] are both modulo 109+7 and we cannot guarantee the former is larger than the later. Also, ` % ` operator in java is modulo rather than remainder, so ` negative % mod is negative`

• Hi, Thank you for your answer. And could you tell me why k have to smaller than n*(n-1)?

• @tumaolin94 because that's the max number of reverse pairs you could get from an array of size n, where every pair of number is in reverse order, i.e the whole array is in descending order.

• best explanation I have seen for this problem!

dp[i][j] = (dp[i][j]+mod) % mod;

Why the will be error when n and k are very large?

dp[i][j] = dp[i][j] % mod;

• @JiawenQi98 please see my reply to johirbuet above. Basically the dp[i][j] -= dp[i-1][j-i] line might result in negative number since dp[i][j] and dp[i-1][j-i] are both modulo.

• @dreamchase Thanks! Understand!

• This post is deleted!

• This post is deleted!

• dp[n][k] = dp[n][k-1]+dp[n-1][k]-dp[n-1][k-n] since this is your formula.

Why dp[i][j] can equals to "dp[i][j-1] + dp[i-1][j]; "
Should we prove that

when k<n
dp[n][k] = dp[n][k-1]+dp[n-1][k] ?

• @dreamchase thx,i get it

• Hi @dreamchase your solution is really smart~ Just one question, is there a reason for i starting at 3? I think for (int i = 1; i <= n; i++) also works

• Anyone have a good approach on solving these types of problems? DP problems like these are the only ones where I just can't figure out how to move on. I try to see if I can create subproblems, but it's not obvious to me

• @ya_ch_yv because we are processing pairs. One valid pair is made up of at least two numbers. For arrays of two elements, dp[2][0]，dp[2][1] is done for that. So program starts from 3.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.