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


  • 14

    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 minusdp[i-1][j-i], because everyj >= iin 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;
    };
    

  • 0
    This post is deleted!

  • 0
    F

    @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?


  • 0
    This post is deleted!

  • 0

    @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


  • 0
    D

    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!


  • 0

    @darren5
    Honestly, I do not understand your questions...I hope the following answer will help you.

    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).


  • 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


  • 0
    R

    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.


  • 3

    @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 add5 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]


  • 3
    D

    @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]


  • 0
    H
    This post is deleted!

  • 0
    H
    This post is deleted!

Log in to reply
 

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