⚡Flashcard Drill➔
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

  1. Let dp[i] be a dictionary mapping a common difference d to the number of arithmetic subsequences of length at least 2 that end at index i with difference d.
  2. For each earlier index j, compute d = nums[i] - nums[j]; every subsequence counted in dp[j][d] extends to a length-3-or-more subsequence ending at i.
  3. Add that count dp[j][d] to the answer, then store dp[i][d] += dp[j][d] + 1, where the +1 is the length-2 pair (j, i).
  4. 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 +1 but must never be added to the answer; only cnt from dp[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 d can 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems