K Inverse Pair Array

[csujedihy]

Idea:

You can just write down some the cases from 1 to 4 and you will find the pattern which is actually combinations.
Like when i = 4, you can just insert 4 to all the cases in a proper position when i = 3 to get the number of results when i=4.
Note that i limits the number of places you can do the insertion. If i = 5, there is only 5 places you can insert.
So you start from i = 0 as base case and you can get the final result at the end.

This is what we get from the above conclusion.

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

But if you want to get your solution accepted in Python, then you need more optimization (BTW: I think is unfair since C++'s solution can pass it).
Actually, the above formula does have lots of redundant computation. As you can see, fordp[i][j]and dp[i][j-1], we may use dp[i-1][j-1], dp[i-1][j-2],...,dp[i-1][j-i+1] twice. Thus, I rewrite the formula as follows.

dp[i][j] = dp[i][j-1] + dp[i-1][j] - (if j - i >= 0: dp[i-1][j-i] else: 0)

It works like a sliding window, adding dp[i-1][j] to dp[i][j-1] and then reducing dp[i-1][j-i] if applicable to remain a sliding window whose size is i.

O(nk) space solution

class Solution(object):
    def kInversePairs(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        MOD = 10**9 + 7
        upper = n * (n - 1) / 2
        if k == 0 or k == upper:
            return 1
        if k > upper:
            return 0
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            dp[i][0] = 1
            for j in range(k + 1):
                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
        return dp[n][k]

O(k) space solution

class Solution(object):
    def kInversePairs(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        MOD = 10**9 + 7
        upper = n * (n - 1) / 2
        if k == 0 or k == upper:
            return 1
        if k > upper:
            return 0
        dp = [0] * (k + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            temp =[1] + [0] * k
            for j in range(k + 1):
                temp[j] = (temp[j-1] + dp[j]) % MOD
                if j - i >= 0:
                    temp[j] = (temp[j] - dp[j - i]) % MOD
            dp = temp
        return dp[k]