# Shared my C++ O(n * k) solution with explanation

• 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;
};
``````

• This post is deleted!

• @yangyx
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

don't understand this piece of code. can you explain?

• This post is deleted!

• @fiveface
Consider this situation

``````1. Dp[i-1][j-i] < mod.
2. Before Dp[i][j] % mod, Dp[i][j] > mod,
3. After we did Dp[i][j] % mod, It give a chance to less than Dp[i-1][j-i]
``````

That is to say It is possible

``````Dp[i][j] < Dp[i-1][j-1],
and (dp[i][j] - dp[i-1][j-i] ) % mod < 0,
``````

This is a negative number, not the answer we want, So, We must + mod

• I can't understand for j>=i case.
in case of j>=i, i think dp[i][j] = 0. this is not true ? how can we make more than N pair in size N array ?
according to the judge, dp[3][3] = 0, dp[3][4] = 0!

• @darren5

Dp[3][3] = 1 not =0, and Dp[3][4] = 0

You know Dp[3][3] mean the number of permutations of(1..3) with 3 inverse pairs, right?

Obviously, Arrays consist of numbers from (1..3) and have 3 inverse pair is [3, 2, 1].
and the inverse pairs are (3, 2), (3,1), (2, 1).

• @darren5

There are the DP matrix of n = 4, k = 8.

n \ k 1 2 3 4 5 6 7 8
1 1 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0
3 1 2 2 1 0 0 0 0
4 1 3 5 6 5 3 1 0

In size N array have at most m + N - 1 inverse pairs , If size N-1 array have at most m inverse pairs

• Very nice solution, thanks for posting. It is very hard to come up with the approach. Could you please post how you came up with the approach or what was the thought process for dp[i][m] = (dp[i][m] + dp[i-1][m-j]) or was it by just taking examples.

• @rishp
OK~ , I will repeat consicely what I said above.

1. At first glance see this problem, I consider can be solved by dynamic programming. Because there is a potential connection between the number of permutations of `(1..n)` and `(1...n-1)`

2. But the difficulty is how can we find the `connection`, (I like to call it recursion formula). So we must define a meaning about dp[i][j], and get the connection between `dp[i][j]` next `dp[][]` (How can I figure out the meaning, emmmm..just experience, Sorry, I don't know how to said, You can do more dynamic programming problems ：） )

3. When I figured out the meaning about `dp[i][j]` which represents the number of `permutations of (1...n)`with k inverse pairs, I want to find the connection. As I said in before.

• 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
4. if we know the value of `dp[4][0]` to `dp[4][7]`.

• We can get `dp[5][0]` = `dp[4][0]` (permutations of (1...5) with 0 inverse pairs, We must add 5 in permutations of (1..4) with 0 inverse pair,
• `dp[5][1] = dp[4][0] + dp[4][1]` that mean, we want to get the permutations of (1...5) with 1 inverse pair, We can get it from permutations of (1..4) with 0 inverse pair and add 1 inverse pair in it, also , We can get it from permutations of (1..4) with 1 inverse pair and add 0 inverse pair in it.
• .... So, We can compute dp[5][j] thought dp[4][], and that is
`dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-2] + ..... +dp[i-1][j - i + 1]`
1. But the above Dp process We have to finish it in O(n * k * k ). We have to optimized it ... I would copy my post above due to I have other work to do..
• 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]` with `dp[i][j] = dp[i][j-1] +dp[i-1][j]`

• So, how about `j >= i` ? if we still use `dp[i][j] = dp[i][j-1] +dp[i-1][j]`, We must minus the "redundant dp",
For example （Make sure you understand the meaning of the above formula）, We want to compute `dp[i][5] = dp[i][4] + d[i-1][5]` , But we know add `5 in permutation (1..4)` at most add `4` inverse pair, So, you can not find a position to add`5` in `array[1, 2, 3, 4] (0 inverse pair)`and get the permutation with 5 inverse pairs . So If j >= i the formula would be this `(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]`

• @SYSU---yyx

Mathematical Proof:
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ......+dp[i-1][j-i+1] as per definition ---(1)

But dp[i][j-1] = dp[i-1][j-1] + dp[i-1][j-2] + ....+ dp[i-1][j-i] as per definition ---(2)

From (1) and (2)

dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] + ......+dp[i-1][j-i+1]) + dp[i-1][j-i] - dp[i-1][j-i]
=>dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] + ......+dp[i-1][j-i+1] + dp[i-1][j-i]) - dp[i-1][j-i]
=>dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-i]

• This post is deleted!

• This post is deleted!

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