## 题目描述：

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].

## 解题思路：

```k   c
0 1 1```

```k   c
0 1 1
1 1 1```

```k       c
0 1     1
1 1 1   2
2   1 1 2
3     1 1```

```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```

```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
``````

Pingbacks已关闭。