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