K Inverse Pairs Array

Intuition

Solution

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        """
        I(n, k) = I(n-1, k) + I(n-1, k-1) + I(n-1, k-2) + I(n-1, k-3) + I(n-1, max(0, k - (n - 1)))
        """
        dp = [0] * (k + 1)
        dp[0] = 1
        mod = 10 ** 9 + 7
        for i in range(2, n + 1):
            tmp = []
            s = 0
            for j in range(k + 1):
                s += dp[j]
                if j - i >= 0:
                    s -= dp[j - i]
                s = s % mod
                tmp.append(s)
            dp = tmp
        return dp[k]