题目链接：629. K个逆序对数组
动态规划。递推公式很难推，建议直接看题解。
class Solution:
def kInversePairs(self, num: int, key: int) -> int:
# dp[n][k] = dp[n-1][k] + dp[n][k-1] - dp[n-1][k-n]
# dp[0]][0] = 1
MOD = 10 ** 9 + 7
dp = [[1] + [0] * key, [0] * (key + 1)]
for n in range(1, num + 1):
cur, prev = n % 2, (n - 1) % 2
for k in range(0, key + 1):
dp[cur][k] = (dp[prev][k] + (dp[cur][k - 1] if k - 1 >= 0 else 0) - (
dp[prev][k - n] if k - n >= 0 else 0)) % MOD
return dp[num % 2][key]