629. K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

First version

@cache
def kInversePairs(self, n: int, k: int) -> int:
    M = 1000000007
    if n == 0:
        return 0
    if k == 0:
        return 1
    res = 0
    # first is the first value in the array
    for first in range(1, min(n + 1, k + 2)):
        res += self.kInversePairs(n - 1, k - first + 1) % M
    return res % M
  • dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]
  • It's possible that some where in the right hand side the second array index become negative, since we cannot generate negative inverse pairs we just treat them as 0, but still leave the item there as a place holder.
  • dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]
  • dp[n][k+1] = dp[n-1][k+1]+dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]
  • so by deducting the first line from the second line, we have dp[n][k+1] = dp[n][k]+dp[n-1][k+1]-dp[n-1][k+1-n]
@cache
def kInversePairs(self, n: int, k: int) -> int:
    M = 1000000007
    if n == 0:
        return 0
    if n == 1 and k > 0:
        return 0
    if k == 0:
        return 1
    if k < 0:
        return 0
    return (self.kInversePairs(n, k - 1) + self.kInversePairs(n - 1, k) - self.kInversePairs(n - 1, k - n)) % M