- 软件开发
- 【Leetcode】413. Arithmetic Slices
class Solution1(object):
def numberOfArithmeticSlices(self
, A
):
"""
注意这道题是求连续的等差数列
连续这个属性使得这道题比较容易解
dp[i]表示以A[i]结尾最长等差数列的个数
两步：
step1:
求出所有最长的等差数列， 使用dp法
step2:
根据每个等差数列的长度求出包含多少子数列
"""
A
.append
(float("inf"))
dp
= [2] * len(A
)
count
= []
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:
if dp
[i
-1] > 2:
count
.append
(dp
[i
-1])
result
= 0
for number
in count
:
result
+= sum([number
+ 1 - c
for c
in range(3, number
+1)])
return result
class Solution2(object):
"""
solution1虽然可以解但是思考过程有点复杂
我们用dp[i]表示以A[i]为结尾的等差数列的长度，那么如果A[i]能与前面的数构成等差数列，
那么dp[i] = dp[i-1] + 1
其中 dp[i-1] 表示以A[i-1]结尾的数列现在以A[i]结尾，+1 表示前取A[i-2],A[i-1]这两个数构成等差数列
"""
def numberOfArithmeticSlices(self
, A
):
dp
= [0] * 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
return sum(dp
)
