這兩天一直復習動態規劃，就想到leetcode上刷刷題，easy難度的很少，大部分都是medium和hard。本題是第一道DP類型medium難度的題目，但是用其他的方法比如暴力法也可以求解。首先來看題目描述：
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
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.
解題思路：
題目描述的很明確，包含至少三個數的序列，如果差分相等，那么這個序列就叫做arithmetic sequence，在一個數組里統計有多少個滿足條件的序列（切片）。首先試試暴力法。我們固定一個最小長度為3的區間(i, j)，如果差分相等，我們就右移j，一直到數組的末尾，滿足條件的話計數加一。需要注意的是如果區間(i, j-1)是arithmetic slice，那么我們末尾加上一個j，如果A[j] - A[j-1] 等于之前的差分值，那么區間(i, j)也屬于arithmetic slice，我們要避免每次判斷都要計算前面的差分。代碼如下：
class Solution(object):def numberOfArithmeticSlices(self, A):res = 0for i in range(len(A)-2):d = A[i+1] - A[i]for j in range(i+2, len(A)):if A[j] - A[j-1] == d:res += 1else:breakreturn res
?當然我們可以用dp算法，令一維dp[i]表示以i結尾的區間有多少個arithmetic ?slice，新添加的元素和前面元素的差，如果等于之前的差值，那么就讓dp[i]加一。代碼如下：
class Solution(object):def numberOfArithmeticSlices(self, A):dp = [0 for i in range(len(A))]res = 0for i in range(2, len(A)):if A[i] - A[i-1] == A[i-1] - A[i-2]:dp[i] = 1 + dp[i-1]res += dp[i]return res
我們可以優化空間復雜度，因為dp的更新只跟上一個元素有關，因此我們用一個變量空間來代替原來的數組。
class Solution(object):def numberOfArithmeticSlices(self, A):dp = 0res = 0for i in range(2, len(A)):if A[i] - A[i-1] == A[i-1] - A[i-2]:dp += 1res += dpelse:dp = 0return res
?
