K Inverse Pairs Array LeetCode solution in Python

1
class Solution:
2
    # A very good description of the dp solution is at
3
    # https://leetcode.com/problems/k-inverse-pairs-array/solution/
4
    # The code below uses two 1D arrays--dp and tmp--instead if a
5
    # 2D array. tmp replaces dp after each i-iteration.
6
    def kInversePairs(self, n: int, k: int) -> int:
7
        dp, mod = [1] + [0] * k, 1000000007
8

9
        for i in range(n):
10
            tmp, sm = [], 0
11
            for j in range(k + 1):
12
                sm += dp[j]
13
                if j - i >= 1:
14
                    sm -= dp[j - i - 1]
15
                sm %= mod
16
                tmp.append(sm)
17
            dp = tmp
18
            # print(dp)       # <-- uncomment this line to get a sense of dp from the print output
19
            #     try n = 6, k = 4; your answer should be 49.
20
        return dp[k]