Started with getting a TLE for Python using O(n) space. This is simply because we're doing a lot of redundant calculations such as adding all the previous cols many times.

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

I did dp[i-1][j-i+1] as the last because you can't insert the current n into a position of the previous n because you ran out of positions to insert. For example, if I want to insert 3 into 12, I only have 3 places to insert my 3.

```
class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
dp=[1]+[0]*k
for i in xrange(2,n+1):
for j in xrange(k,0,-1):
for col in xrange(j-1,j-(i-1)-1,-1):
if 0<=col<=k:
dp[j]+=dp[col]
return dp[-1]
```

- dp[i][j-1]=dp[i-1][j-1]+dp[i-1][j-2]+...+ dp[i-1][j-1-(i-1)]

Combining 1 and 2 with above we get

- dp[i][j]=dp[i-1][j]+dp[i][j-1]- dp[i-1][j-i]

Obviously, j-i>=0 or else it would be out of our bounds.

Then you create solutions like others have on here.