Python DP solution beats 95%


  • 1
    T

    The idea is simple, dp[i][j] stores the number of slices starting with A[i], A[j].

    import collections
    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            n = len(A)
            dp, locs, res = [[0]*n for _ in xrange(n)], collections.defaultdict(list), 0
            for i, num in enumerate(A):
                locs[num] += i,
            for j in xrange(n-2,0,-1):
                for i in xrange(j-1,-1,-1):
                    target = 2*A[j] - A[i]
                    for k in locs.get(target, []):
                        if k > j:
                            dp[i][j] += dp[j][k] + 1
                    res += dp[i][j]
            return res
    

Log in to reply
 

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