629.md

629. K Inverse Pairs Array

Solution 1 (time O(nk), space O(nk))

# Dynamic Progamming
class Solution(object):
    def kInversePairs(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        mod = 10 ** 9 + 7
        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(k + 1):
                dp[i][j] = (dp[i][j - 1] if j - 1 >= 0 else 0)
                dp[i][j] -= (dp[i - 1][j - i] if j - i >= 0 else 0)
                dp[i][j] += dp[i - 1][j]
                dp[i][j] %= mod
        return dp[n][k]