Arithmetic Slices

此题能解的方法太多了，首先利用蛮力O(n^2)的算法都可以AC，这种太trivial就不讲了，这里DP的难度在于需要放弃在一个DP位将所有解法全部记下来的这种思路，虽然大多数DP确实都是这么去写的，这道题需要将思路转换为，每一个DP位只保存以当前对应数为末尾的arithmetic slices，举例3，4，5，6，当到达6时，以前一个元素5结尾的slice只有一个，但是因为4，5，6是连续的，所以相当于在以5为结尾的序列的基础上再加1就是以6位结尾的总数了，当然最大的前提还是4，5，6是连续，所以转移方程写成

dp[i] = dp[i - 1] + 1 if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]

根据上面的方程就能写出最原始的O(n)空间复杂度的DP了

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        dp = [0] * n
        for i in xrange(2, n):
            if A[i] - A[i - 1] == A[i - 1] - A[i - 2]:
                dp[i] = dp[i - 1] + 1

        return sum(dp)

这里明显注意到i只和i - 1的dp值有关，我们可以把空间从O(n)变为O(1)，使用一个dp变量

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        dp = 0
        result = 0
        for i in xrange(2, n):
            if A[i] - A[i - 1] == A[i - 1] - A[i - 2]:
                dp += 1
                result += dp
            else:
                dp = 0
        return result

还有数学类的做法和记忆化搜索的做法，大致都比较雷同，这里就不写了