NeetCode #754LC-446Hard2-D Dynamic Programming
← Back to All Problems#754 · #446 · Arithmetic Slices II - Subsequence(等差数列划分 II - 子序列)
📌 Problem Statement & Constraints
Given an integer array
nums, return the number of arithmetic subsequences of length at least 3. Constraints: 1 <= nums.length <= 1000, -2^31 <= nums[i] <= 2^31 - 1.💡 Core Algorithmic Approaches
- Let
dp[i]be a dictionary mapping a common differencedto the number of arithmetic subsequences of length at least 2 that end at indexiwith differenced. - For each earlier index
j, computed = nums[i] - nums[j]; every subsequence counted indp[j][d]extends to a length-3-or-more subsequence ending ati. - Add that count
dp[j][d]to the answer, then storedp[i][d] += dp[j][d] + 1, where the+1is the length-2 pair(j, i). - The length-2 pairs are stored but never added to the answer, which is exactly the length-at-least-3 requirement.
💻 Benchmark Python3 Implementation
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
dp = [dict() for _ in range(n)]
total = 0
for i in range(n):
for j in range(i):
d = nums[i] - nums[j]
cnt = dp[j].get(d, 0)
total += cnt # each extends to a length >= 3 slice
dp[i][d] = dp[i].get(d, 0) + cnt + 1
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): every ordered pair is examined once.
💾 Space Complexity
O(n^2) worst case, since each index stores a dictionary of differences.
⚠️ Interview Pitfalls & Follow-ups
- Counting the length-2 pairs: they are stored via the
+1but must never be added to the answer; onlycntfromdp[j][d]counts. - Using a 2-D array indexed by difference: differences can be as large as 2^32, so a dictionary per index is required.
- Assuming subsequences must be contiguous: they need not be; the DP chains any earlier element sharing the difference.
- Ignoring negative differences: the array may decrease, so
dcan be negative and must be stored as-is.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.