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=+*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.