Java DP O(nk) solution


  • 39

    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];
        }

  • 1
    J

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


  • 4

    @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


  • 0
    T

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


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


  • 0
    M

    best explanation I have seen for this problem!


  • 0
    T

    @dreamchase Thx for your reply.


  • 1
    J

    Can u explain about this

    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;


  • 1

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


  • 0
    J

    @dreamchase Thanks! Understand!


  • 0
    D
    This post is deleted!

  • 0
    D
    This post is deleted!

  • 0

    @dreamchase said in Java DP O(nk) solution:

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


  • 0
    N

    @dreamchase thx,i get it


  • 0
    Y

    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


  • 0
    L

    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


Log in to reply
 

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