⚡Flashcard Drill➔
NeetCode #687LC-2140Medium1-D Dynamic Programming
← Back to All Problems

#687 · #2140 · Solving Questions With Brainpower(解决智力问题)

📌 Problem Statement & Constraints

You are given a 2-D array questions where questions[i] = [points_i, brainpower_i]. Solving question i earns points_i but forces you to skip the next brainpower_i questions; alternatively you may skip it. Return the maximum points obtainable. Constraints: 1 <= questions.length <= 10^5, 1 <= points_i <= 10^5, 0 <= brainpower_i <= 10^5.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the maximum points obtainable from questions i..n-1.
  2. Skipping question i gives dp[i + 1]; solving it gives points_i + dp[i + brainpower_i + 1].
  3. Since the recurrence depends on later indices, fill dp from right to left.
  4. The base case is dp[n] = 0, and the answer is dp[0].

💻 Benchmark Python3 Implementation

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            points, brainpower = questions[i]
            nxt = i + brainpower + 1
            solve = points + (dp[nxt] if nxt < n else 0)
            dp[i] = max(dp[i + 1], solve)
        return dp[0]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single backward pass.
💾 Space Complexity
O(n): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Jumping forward only brainpower steps: the current question is also skipped, so the jump is brainpower + 1.
  • Processing forward: the dependency is on future indices, so the loop must run backwards.
  • Skipping the bounds check on the jump: i + brainpower + 1 may exceed n.
  • Choosing the highest-point questions greedily: a high-value question can block several valuable later ones.
⚡
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 1-D Dynamic Programming Problems