Concise Python DP with space N (instead of N*M)


  • 0
    S

    The general DP idea is to build a 2D matrix where DP[a][b] is the length of the longest common end run of A[0...a] and B[0..b]. (Note that "longest common end run" means start comparing at the end of the arrays and working forward until you get a mis-match.) Then we iterate through the matrix and fill out all the numbers. Instead of scanning backwards over A[0...a] and B[0...b] to see how long that common run is, we just note that if A[a] != B[b] then DP[a][b] = 0 (the subsequences have no tail end in common). If A[a] == B[b] then, instead of stepping backwards and testing A[a-i] == B[b-i] for all i, we simply add 1 to the value of DP[a-1][b-1]. In other words: if the last number of each subsequence matches, then the length of the matching run is one more than the length of matching run when A and B are both shortened by one element ( DP[a-1][b-1] ).

    DP[a][b] = 0 if A[a] != B[b]; otherwise DP[a][b] = DB[a-1][b-1] + 1.

    Instead of using a 2D matrix to store results, the inner loop can write results into an array instead and just keep overwriting the results on each iteration of the outer loop. This reduces storage requirement of len(A)*len(B) to a single array of len(A). So we just have DP[a]. However, you'll see that DP[a] depends on the value of DP[a-1] from the previous pass. So, iterate backwards so that writing DP[a] doesn't overwrite the value of DP[a-1] until after it is used.

    A little bit of care needs to be taken to not accidentally access DP[-1].
    Uncomment the print statement to see the algorithm in action.

    class Solution(object):
        def findLength(self, A, B):
            best = 0
            dp = [0]*len(A)
            for b in range(len(B)):
                for a in range(len(A)-1,0,-1):
                    dp[a] = dp[a-1]+1 if A[a]==B[b] else 0
                dp[0] = 1 if A[0]==B[b] else 0
    #            print dp
                best = max(best,max(dp))
            return best
    

Log in to reply
 

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