题目描述：
LeetCode 446. Arithmetic Slices II - Subsequence
A sequence of numbers 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 sequences:
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 subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.
A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.
The function should return the number of arithmetic subsequence slices in the array A.
The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.
Example:
Input: [2, 4, 6, 8, 10] Output: 7 Explanation: All arithmetic subsequence slices are: [2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10]
题目大意：
如果一组长度至少为3的数，两两连续元素之差都相等，则称其为等差数列。
给定包含N个元素，起始下标为0的数组A。子序列切片是指任意整数序列(P0, P1, ..., Pk)满足0 ≤ P0 < P1 < ... < Pk < N。
如果A[P0], A[P1], ..., A[Pk-1], A[Pk]是等差序列，则数组A的子序列切片 (P0, P1, ..., Pk) 为等差子序列切片。特别的，k ≥ 2。
函数应当返回数组A的等差子序列切片个数。
输入包含N个整数。每一个整数范围为[ -2^31, 2^31 - 1 ]，并且 0 ≤ N ≤ 1000。输出确保小于 2^31-1。
解题思路：
动态规划（Dynamic Programming）
状态转移方程：dp[x][delta] += dp[y][delta] + 1（y∈[0, x - 1]）
dp[x][delta]表示以第x个元素结尾，且公差为delta的等差子序列切片个数。
Python代码：
class Solution(object):
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
size = len(A)
ans = 0
dp = [collections.defaultdict(int) for x in range(size)]
for x in range(size):
for y in range(x):
delta = A[x] - A[y]
dp[x][delta] += 1
if delta in dp[y]:
dp[x][delta] += dp[y][delta]
ans += dp[y][delta]
return ans
本文链接：http://bookshadow.com/weblog/2016/11/06/leetcode-arithmetic-slices-ii-subsequence/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
