8.22 - hard - 86

446. Arithmetic Slices II - Subsequence

一道dp的题目

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        total = 0
        dp = [collections.defaultdict(int) for item in A]
        # dp[i][j] stores the number of arithmetic slices (including those with only length 2) whose constant difference is j ending at i
        for i in range(len(A)):
            for j in range(i):
                gap = A[i] - A[j]
                dp[i][gap] += 1
                if gap in dp[j]:
                    dp[i][gap] += dp[j][gap]
                    total += dp[j][gap]
        return total