题目描述：
LeetCode 629. K Inverse Pairs Array
Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.
Since the answer may very large, the answer should be modulo 109 + 7.
Example 1:
Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.
Example 2:
Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
Note:
The integer n is in the range [1, 1000] and k is in the range [0, 1000].
题目大意：
求数字1到n的排列中，逆序对个数恰好为k的排列数
解题思路：
求递推式，时间复杂度O(n * k)
观察下列推导过程：
当n=1时，k的取值范围是[0, 0]
k c 0 1 1
当n=2时，k的取值范围是[0, 1]
k c 0 1 1 1 1 1
当n=3时，k的取值范围是[0, 3]
k c 0 1 1 1 1 1 2 2 1 1 2 3 1 1
当n=4时，k的取值范围是[0, 6]
k c 0 1 1 1 2 1 3 2 2 2 1 5 3 1 2 2 1 6 4 1 2 2 5 5 1 2 3 6 1 1
当n=5时，k的取值范围是[0, 10]
k c 0 1 1 1 3 1 4 2 5 3 1 9 3 6 5 3 1 15 4 5 6 5 3 1 20 5 3 5 6 5 3 22 6 1 3 5 6 5 20 7 1 3 5 6 15 8 1 3 5 9 9 1 3 4 10 1 1
Python代码：
class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
MOD = 10**9 + 7
dp = [1]
for x in range(2, n + 1):
ndp = []
num = 0
for y in range(min(1 + x * (x - 1) / 2, k + 1)):
if y < len(dp): num = (num + dp[y]) % MOD
if y >= x: num = (MOD + num - dp[y - x]) % MOD
ndp.append(num)
dp = ndp
return k < len(dp) and dp[k] or 0
本文链接：http://bookshadow.com/weblog/2017/06/25/leetcode-k-inverse-pairs-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
