Leetcode 629 Solution

This article provides solution to leetcode question 629 (k-inverse-pairs-array).
Categories:
Tags:
Access this page by simply typing in "lcs 629" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/k-inverse-pairs-array

Solution

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        dp = []
        s = []

        for i in range(n + 1):
            dp.append([0] * (k + 1))
            s.append([0] * (k + 1))

        for i in range(n + 1):
            dp[i][0] = 1
            s[i][0] = 1

        for j in range(1, k + 1):
            dp[1][j] = 0
            s[1][j] = s[1][j - 1] + dp[1][j]

        for i in range(2, n + 1):
            for j in range(1, k + 1):
                dp[i][j] = (s[i - 1][j] - (s[i - 1][j - i] if j >= i else 0)) % (10 ** 9 + 7)
                s[i][j] = s[i][j - 1] + dp[i][j]

        return dp[n][k]