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
