Problem Description

You are given a list of exam questions, where each question has two properties: the points you can earn by solving it, and the "brainpower" cost that determines how many subsequent questions you must skip if you solve it.

The questions are represented as a 2D array questions, where questions[i] = [points_i, brainpower_i]:

• points_i is the number of points you earn if you solve question i
• brainpower_i is the number of questions immediately after question i that you cannot solve if you choose to solve question i

You must process the questions in order (starting from question 0) and for each question, you have two choices:

1. Solve it: You earn points_i points, but you must skip the next brainpower_i questions
2. Skip it: You don't earn any points from this question, but you can move on to consider the next question

For example, with questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:

• If you solve question 0, you earn 3 points but must skip questions 1 and 2 (the next 2 questions due to brainpower = 2)
• If you skip question 0 and solve question 1, you earn 4 points but must skip questions 2 and 3 (the next 3 questions due to brainpower = 3)

The goal is to find the maximum total points you can earn by strategically choosing which questions to solve and which to skip.

Intuition

The key insight is that at each question, we face a decision: solve it or skip it. This binary choice structure naturally leads us to think about dynamic programming or recursion.

Let's think about this problem from any position i in the questions array. At position i, we need to make the optimal decision to maximize our total points from this position onwards. We have two options:

1. Solve question i: We gain points[i] points immediately, but then we're forced to skip the next brainpower[i] questions. So our next decision point would be at position i + brainpower[i] + 1.

2. Skip question i: We don't gain any points from this question, but we can immediately move to the next question at position i + 1.

The maximum points we can get from position i onwards is the better of these two choices:

• points[i] + maxPoints(i + brainpower[i] + 1) if we solve it
• maxPoints(i + 1) if we skip it

This recursive structure reveals that we're dealing with overlapping subproblems. For instance, different decision paths might lead us to the same question index later on. If we solve question 0 and it forces us to skip to question 3, or if we skip questions 0, 1, and 2 to reach question 3, we'd be calculating the maximum points from question 3 onwards multiple times.

To avoid redundant calculations, we can use memoization to cache the results. This transforms our solution into a dynamic programming approach where dfs(i) represents the maximum points obtainable starting from question i, and we work our way backwards through the questions, building up our solution from the base case (when i >= n, meaning no more questions left, return 0).

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using a top-down dynamic programming approach with memoization. Here's how the implementation works:

1. Define the Recursive Function

We create a function dfs(i) that calculates the maximum points obtainable starting from the i-th question. This function represents our state at each position in the questions array.

2. Base Case

When i >= len(questions), we've gone beyond the last question, meaning there are no more questions to process. In this case, we return 0 as no more points can be earned.

3. Recursive Case

For each valid question index i, we extract:

• p: the points for solving this question (questions[i][0])
• b: the brainpower cost, i.e., number of questions to skip (questions[i][1])

Then we calculate:

max(p + dfs(i + b + 1), dfs(i + 1))

This represents choosing the maximum between:

• Solving the current question: gain p points and jump to question i + b + 1 (skipping b questions after the current one)
• Skipping the current question: gain no points but move to the next question i + 1

4. Memoization with @cache

The @cache decorator automatically memorizes the results of dfs(i) for each value of i. This prevents redundant calculations when the same state is reached through different paths. For example, if multiple decision sequences lead to evaluating question 5, we only calculate dfs(5) once.

5. Return the Result

We start the recursion with dfs(0), which gives us the maximum points starting from the first question (index 0).

The time complexity is O(n) where n is the number of questions, as each state is computed at most once due to memoization. The space complexity is also O(n) for the recursion stack and the cache storage.

Example Walkthrough

Let's walk through a small example with questions = [[3, 2], [4, 3], [4, 4], [2, 5]].

We'll trace through the recursive calls starting from dfs(0):

Step 1: dfs(0) - Processing question 0 [3, 2]

• Option 1: Solve it → earn 3 points, skip 2 questions, continue from index 3
  • This gives us: 3 + dfs(3)
• Option 2: Skip it → earn 0 points, continue from index 1
  • This gives us: dfs(1)
• Return: max(3 + dfs(3), dfs(1))

Step 2: dfs(3) - Processing question 3 [2, 5]

• Option 1: Solve it → earn 2 points, skip 5 questions, continue from index 9
  • Since index 9 >= 4 (out of bounds), dfs(9) = 0
  • This gives us: 2 + 0 = 2
• Option 2: Skip it → continue from index 4
  • Since index 4 >= 4 (out of bounds), dfs(4) = 0
  • This gives us: 0
• Return: max(2, 0) = 2

Step 3: dfs(1) - Processing question 1 [4, 3]

• Option 1: Solve it → earn 4 points, skip 3 questions, continue from index 5
  • Since index 5 >= 4 (out of bounds), dfs(5) = 0
  • This gives us: 4 + 0 = 4
• Option 2: Skip it → continue from index 2
  • This gives us: dfs(2)
• Return: max(4, dfs(2))

Step 4: dfs(2) - Processing question 2 [4, 4]

• Option 1: Solve it → earn 4 points, skip 4 questions, continue from index 7
  • Since index 7 >= 4 (out of bounds), dfs(7) = 0
  • This gives us: 4 + 0 = 4
• Option 2: Skip it → continue from index 3
  • We already computed dfs(3) = 2 (memoization helps here!)
  • This gives us: 2
• Return: max(4, 2) = 4

Backtracking the results:

• dfs(2) = 4
• dfs(1) = max(4, 4) = 4
• dfs(3) = 2
• dfs(0) = max(3 + 2, 4) = max(5, 4) = 5

The maximum points we can earn is 5, achieved by solving question 0 (earning 3 points), skipping questions 1 and 2 (due to brainpower cost), and then solving question 3 (earning 2 points).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of questions. This is achieved through memoization with the @cache decorator. Each state i (representing the index of the current question) is computed at most once. Since there are n possible states (indices from 0 to n-1), and each state performs O(1) operations (comparing two values and making recursive calls), the total time complexity is O(n).

The space complexity is O(n), where n is the number of questions. This consists of two components:

1. The recursion call stack can go up to depth O(n) in the worst case when we skip every question (calling dfs(i+1) repeatedly).
2. The memoization cache stores up to n different states (one for each possible index value).

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Calculation Error When Solving a Question

The Pitfall: A frequent mistake is incorrectly calculating the next available question index after solving the current one. Developers often write:

• dfs(index + brainpower) instead of dfs(index + brainpower + 1)

This error stems from misunderstanding what brainpower represents. If brainpower = 2, it means we skip the next 2 questions AFTER the current one, not including the current question itself.

Example of the Bug:

# INCORRECT
solve_current = points + dfs(index + brainpower)  # Wrong!

With questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:

• Solving question 0 (index 0) with brainpower 2 should skip to question 3 (index 3)
• The correct calculation: next_index = 0 + 2 + 1 = 3
• The incorrect calculation: next_index = 0 + 2 = 2 (would incorrectly allow solving question 2)

Solution: Always use index + brainpower + 1 to correctly skip past the required number of questions:

# CORRECT
solve_current = points + dfs(index + brainpower + 1)

2. Missing or Incorrect Memoization

The Pitfall: Without memoization, the recursive solution has exponential time complexity O(2^n) because the same subproblems are solved multiple times. Some developers might:

• Forget to add memoization entirely
• Try to implement manual memoization but make errors in the dictionary management
• Use memoization incorrectly with mutable default arguments

Example of the Bug:

# INCORRECT - No memoization
def mostPoints(self, questions):
    def dfs(index):
        if index >= len(questions):
            return 0
        points, brainpower = questions[index]
        return max(points + dfs(index + brainpower + 1), dfs(index + 1))
    return dfs(0)

Solution: Use Python's @cache decorator for automatic memoization, or implement a proper memoization dictionary:

# Option 1: Using @cache (recommended)
@cache
def dfs(index):
    # ... implementation

# Option 2: Manual memoization
def mostPoints(self, questions):
    memo = {}
    def dfs(index):
        if index in memo:
            return memo[index]
        if index >= len(questions):
            return 0
        points, brainpower = questions[index]
        memo[index] = max(points + dfs(index + brainpower + 1), dfs(index + 1))
        return memo[index]
    return dfs(0)

3. Incorrect Base Case Handling

The Pitfall: Using index == len(questions) instead of index >= len(questions) in the base case. This causes an index out of bounds error when the brainpower value causes us to skip beyond the array length.

Example of the Bug:

# INCORRECT
if index == len(questions):  # This will miss cases where index > len(questions)
    return 0

If we have 4 questions and solve question 2 with brainpower 3, we jump to index 2 + 3 + 1 = 6, which is greater than 4. The equality check would fail and try to access questions[6], causing an error.

Solution: Always use >= to handle all cases where we've moved past the valid question range:

# CORRECT
if index >= len(questions):
    return 0