8.27 - hard - 109

629. K Inverse Pairs Array
递推公式如下
f(n,k) = sum(f(n-1,i)), where max(k-n+1,0) <= i <= k
f(0,k) = 0
f(n,0) = 1

def kInversePairs(self, n, k):
        dp = [1] + [0] * k
        for i in range(2, n + 1):
            for j in range(1, k + 1): dp[j] += dp[j - 1]
            for j in range(k, 0, -1): dp[j] -= j - i >= 0 and dp[j - i]
        return dp[k] % (10**9 + 7)