446. Arithmetic Slices II - Subsequence
给你一个 integer array，要你回传他的等差 subsequences 的总数
Example 1:
Input: nums = [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]
思路:
1.看 array size 再加上是 subsequence 感觉很适合用 DP
如果说已经算出来 dp[nums[i]] 的结果(以nums[i]为结尾的等差数列个数)
要怎么去更新 dp[nums[j]], j>i ?
首先因为是等差数列 公差是固定的 所以 dp[nums[i]] 中会有很多不同公差的等差数列
如果要在 nums[i] 后面接上 nums[j] 前面的公差就必须是 nums[j]-nums[i]
所以 dp[nums[i]] 不能只记总数 要把不同公差的等差数列数量分开记
也就是用 dp[nums[i]][diff] 代表以 nums[i] 结尾 公差是 diff 的等差数列总数
去更新 dp[nums[j]][diff] 其中 diff = nums[j] - nums[i]
2.照定义 等差数列至少要有三项 所以更新总数的时候要稍微处理一下
假如现在要更新 dp[nums[j]][diff] += dp[nums[i]][diff] + 1
意思是把那些公差是 diff 结尾是 nums[i] 的等差数列后面都接上 nums[j]
然后最后的 + 1 是单指 [nums[i], nums[j]] 这个 subsequence
他的公差也是 nums[j] - nums[i] 只是长度还不够 不能算进总数里
所以总数只需要 += dp[nums[i]][diff]
3.因此流程就是 iterate nums[i] 用比 i 小的 index 去更新 dp[nums[i]][diff]
顺便算出总数 复杂度 O(n^2)
Python code:
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
dp = [defaultdict(int) for i in range(n)]
res = 0
for i in range(n):
for j in range(i):
diff = nums[i] - nums[j]
dp[i][diff] += dp[j][diff] + 1
res += dp[j][diff]
return res