From TLE to working solution: my thinking process


  • 0
    L

    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.

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

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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.