# Java O(nk) Time O(k) Space DP Solution

• ``````public static int kInversePairs(int n, int k) {
int[] dp = new int[k+1];
dp[0] = 1; int mod = 1000000007;
for (int i=1;i<=n;i++) {
int[] temp = new int[k+1];
for (int j=0;j<=k;j++) {
if (j==0) temp[j] = 1;
else {
temp[j] = temp[j-1] + dp[j];
temp[j] %= mod;
if (j >= 1 + Math.min(i-1, j))  temp[j] += mod - dp[j-1-Math.min(i-1, j)];
temp[j] %= mod;
}
}
dp = temp;
}
return dp[k];
}
``````

• how come you had : 1 + Math.min(i-1, j)

``````if (j >= 1 + Math.min(i-1, j))  temp[j] += mod - dp[j-1-Math.min(i-1, j)];
``````

I think j >= i is enough , because if j >=i then j > i-1 , then Math.min(i-1, j) = i-1, so your condition reduce to j >= i.

here is my AC:

``````public int kInversePairs(int n, int k) {
int[][] inverse = new int[2][k+1];
inverse[0][0] = 1;
int mod = 1000000007;
/**
* inverse[n+1][k] = inverse[n][k] + inverse[n][k-1] + ... + inverse[n][k-n]
* inverse[n+1][k-1] =               inverse[n][k-1] + ... + inverse[n][k-n] + inverse[n][k-n-1]
*
* so inverse[n+1][k] = inverse[n+1][k-1] + inverse[n][k] - inverse[n][k-n-1];
*
* so inversen[n][k] = inverse[n][k-1] + inverse[n-1][k] + inverse[n-1][k-n];
*
**/

for (int i = 1; i <= n; i++) {
inverse[1][0] = 1;
for (int j = 1; j <= k; j++) {
inverse[1][j] = inverse[1][j-1] + inverse[0][j];
inverse[1][j] %= mod;
if (j >= i) {
inverse[1][j] += mod - inverse[0][j-i];
inverse[1][j] %= mod;
}
}
int[] tmp = inverse[0];
inverse[0] = inverse[1];
inverse[1] = tmp;
}
return inverse[0][k];
}
``````

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