For a better understanding, I would use O(n * k ) space instead of O(k) space. It's easy to write O(k) space version when you understand this DP process.

As @awice said in his Post

For example, if we have some permutation of 1...4

- 5 x x x x creates 4 new inverse pairs
- x 5 x x x creates 3 new inverse pairs

...- x x x x 5 creates 0 new inverse pairs

### O(n * k ^ 2) Solution

We can use this formula to solve this problem

```
dp[i][j] //represent the number of permutations of (1...n) with k inverse pairs.
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-2] + ..... +dp[i-1][j - i + 1]
```

So, We write a O(k*n^2) Solution through above formula like this

```
public:
int kInversePairs(int n, int k) {
vector<vector<int>> dp(n + 1, vector<int>(k+1, 0));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
for(int j = 0; j < i; ++j){ // In number i, we can create 0 ~ i-1 inverse pairs
for(int m = 0; m <= k; ++m){ //dp[i][m] += dp[i-1][m-j]
if(m - j >= 0 && m - j <= k){
dp[i][m] = (dp[i][m] + dp[i-1][m-j]) % mod;
}
}
}
}
return dp[n][k];
}
private:
const int mod = pow(10, 9) + 7;
};
```

But the above solution is too slow, it spends 1000+ms

### O(n * l) Solution

Look back to the above formula.

`dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-2] + ..... +dp[i-1][j - i + 1]`

Let's consider this example

if `i = 5`

```
dp[i][0] = dp[i-1][0] (creates 0 inverse pair)
dp[i][1] = dp[i-1][0] (1) + dp[i-1][1] (0) = dp[i][0] + dp[i-1][1]
dp[i][2] = dp[i-1][0] (2) + dp[i-1][1] (1) + dp[i-1][2] (0) = dp[i][1] + dp[i-1][2]
.
.
.
dp[i][4] = dp[i-1][0] (4) + dp[i-1][1] (3) + dp[i-1][2] (2) + dp[i-1][3] (1) + dp[i-1][4] (0) = dp[i][3] + dp[i-1][4]
```

Can you find the rules about above formula.

if `j < i`

, we can compute `dp[i][j] = dp[i][j-1] +dp[i-1][j]`

So, how about `j >= i`

We know if we add number i into permutation(0 .. i -1 ), i can create 0 ~i -1 inverse pair

If `j >= i`

, we still use `dp[i][j] = dp[i][j-1] +dp[i-1][j]`

.

We must minus `dp[i][j-i]`

. (In fact it minus`dp[i-1][j-i]`

, because every`j >= i`

in dp vecor,it minus `dp[i-1][j-i]`

individually)

For example, if `i = 5`

`dp[i][5] = dp[i][4] + dp[i-1][5] - dp[i-1][0]`

`dp[i][6] = dp[i][5] + dp[i-1][6] - dp[i-1][1]`

reference code

```
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<int>> dp(n+1, vector<int>(k+1));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
dp[i][0] = 1;
for(int j = 1; j <= k; ++j){
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod;
if(j - i >= 0){
dp[i][j] = (dp[i][j] - dp[i-1][j-i] + mod) % mod;
//It must + mod, If you don't know why, you can check the case 1000, 1000
}
}
}
return dp[n][k];
}
private:
const int mod = pow(10, 9) + 7;
};
```