#### Idea:

You can write down some the cases from 1 to 4 and you will find the pattern.

Like when `i = 4`

, you insert 4 to all the cases in a proper position when `i = 3`

to get the number of results when `i=4`

.

Note that `i`

limits the number of places you can do the insertion. If `i = 5`

, there is only `5`

places you can insert.

So you start from `i = 0`

as base case and you can get the final result at the end.

This is what we get from the above conclusion.

`dp[i][j] = dp[i-1][j - i + 1] + dp[i-1][j - i + 2] + ... + dp[i-1][j]`

But if you want to get your solution accepted in Python, then you need more optimization (BTW: I think is unfair since C++'s solution can pass it).

Actually, the above formula does have lots of redundant computation. As you can see, for`dp[i][j]`

and`dp[i][j-1]`

, we may use `dp[i-1][j-1], dp[i-1][j-2],...,dp[i-1][j-i+1]`

twice. Thus, I rewrite the formula as follows.

`dp[i][j] = dp[i][j-1] + dp[i-1][j] - (if j - i >= 0: dp[i-1][j-i] else: 0)`

It works like a sliding window, adding `dp[i-1][j]`

to `dp[i][j-1]`

and then reducing `dp[i-1][j-i]`

if applicable to remain a sliding window whose size is `i`

.

O(nk) space solution

```
class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
MOD = 10**9 + 7
upper = n * (n - 1) / 2
if k == 0 or k == upper:
return 1
if k > upper:
return 0
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
dp[i][0] = 1
for j in range(k + 1):
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD
if j - i >= 0:
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD
return dp[n][k]
```

O(k) space solution

```
class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
MOD = 10**9 + 7
upper = n * (n - 1) / 2
if k == 0 or k == upper:
return 1
if k > upper:
return 0
dp = [0] * (k + 1)
dp[0] = 1
for i in range(1, n + 1):
temp =[1] + [0] * k
for j in range(k + 1):
temp[j] = (temp[j-1] + dp[j]) % MOD
if j - i >= 0:
temp[j] = (temp[j] - dp[j - i]) % MOD
dp = temp
return dp[k]
```