K Inverse Pairs Array

#Bottom up DP
'''
Intuition:
Consider a sorted array of length n. Now fix the position of the smallest element, by iterating from 1 to n keeping the remaining array intact.
For eg. For n = 3, take [1, 2, 3], fix positions of 1 so: [1, 2, 3], [2, 1, 3] and [2, 3, 1]
For each of these permutations there are already some reverse pairs equal to index of smallest element like for:
[1, 2, 3] => 0 reverse pairs
[2, 1, 3] => 1 reverse pairs
[2, 3, 1] => 2 reverse pairs
So inorder to make k reverse pairs for each of them we need to now find the arrangement of remaining n-1 elements with k-i reverse pairs (i being the no. of reverse pairs already in permutation). Now no matter how we arrange these n-1 elements the reverse pairs they are going to form with the smallest element (the excluded one) will remain i.
'''

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = int(1e9+7)

#Memoization
        """
        @lru_cache(None)
        def solve(n, k):
            if k == 0:
                return 1

            if n == 1:
                return 0

            ans = 0
            for i in range(min(n, k+1)):
                ans += solve(n-1, k-i)%MOD

            return ans%MOD

        return solve(n, k)
        """

        dp = [0]*(k+1) #for n = 1
        dp[0] = 1 #for k = 1
        for i in range(2, n+1):
            tmp = [0]*(k+1)
            slidingSum = 0
            for j in range(k+1):
                slidingSum += dp[j]%MOD
                if j >= i:
                    slidingSum -= dp[j-i]%MOD
                tmp[j] = slidingSum%MOD
            dp = tmp[:]
        return dp[-1]%MOD