LeetCode 446. Arithmetic Slices II - Subsequence

本文主要是介绍LeetCode 446. Arithmetic Slices II - Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道长得一副dp的样子的dp题。

这道题难度不算特别大，因为看得出来肯定是dp题。因为，一个等差序列里面有好几个小的等差序列。
例如，2 4是一个等差序列，2 4 6是一个等差序列。
所以我们发现等差序列是可以扩展的。

那么就得到了，咱们的转移方程的一部分

$$dp[i][delta] = dp[j][delta] + 1$$
其中i，j是表示该数在原序列中的位置,+1表示的是A[i]本身。

然后，因为A[i]这个数可能存在多个前缀序列，所以j的范围应该是[0,i-1]。

从而得到转移方程

$$dp[i][delta] = \sum_{j=0}^{n-1}dp[j][delta] + 1$$

写代码的时候注意一下，delta的范围比较大，为$[-2^{31},2^{31}-1]$。所以不能用一般的二维数组，用C++的话，估计要用map，用python的话要用元组。

class Solution(object):def numberOfArithmeticSlices(self, A):""":type A: List[int]:rtype: int"""ans, n = 0, len(A)dp = [{} for i in xrange(n)]for i in xrange(1, n):for j in range(i):dist = A[i] - A[j]s = dp[j].get(dist, 0) + 1dp[i][dist] = dp[i].get(dist, 0) + sres += (s-1)return ans

这篇关于LeetCode 446. Arithmetic Slices II - Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---