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
- Let
dp[i]be the maximum points obtainable from questionsi..n-1. - Skipping question
igivesdp[i + 1]; solving it givespoints_i + dp[i + brainpower_i + 1]. - Since the recurrence depends on later indices, fill
dpfrom right to left. - The base case is
dp[n] = 0, and the answer isdp[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
brainpowersteps: the current question is also skipped, so the jump isbrainpower + 1. - Processing forward: the dependency is on future indices, so the loop must run backwards.
- Skipping the bounds check on the jump:
i + brainpower + 1may exceedn. - 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.