A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
一道DP基础题，将每一步的记录在数组中就好，例如：
[1,2] DP=[0,0]
[1,2,3] DP=[0,0,1] [1,2,3]
[1,2,3,4] DP=[0,0,1,2] [2,3,4] [1,2,3,4]
[1,2,3,4,5] DP=[0,0,1,2,3] [3,4,5] [2,3,4,5] [1,2,3,4,5]
···
具体解法
class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
dp = [0 for i in range(len(A))]
for i in range(2,len(A)):
if A[i]-A[i-1] == A[i-1]-A[i-2]:
dp[i] = dp[i-1]+1
else:
dp[i] = 0
return sum(dp)
