2140. Solving Questions With Brainpower

Problem Description

In this LeetCode problem, you are presented with a 0-indexed 2D integer array called questions, where each element questions[i] represents a question described by two integers - points_i and brainpower_i. The first integer points_i is the amount of points you'd earn by solving the ith question, and the second integer brainpower_i is the number of subsequent questions you must skip if you decide to solve this question.

The rules of the exam are such that you must make decisions on questions in order, deciding to either solve a question (earning points and skipping the next brainpower_i questions) or to skip it (allowing a decision on the next question). Your goal is to maximize the points you can earn by the end of the exam.

To put it into a scenario, assume questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:

• If you solve the first question, you'll get 3 points but miss out on the next two questions.
• However, if you skip the first question and solve the second one, you'll earn 4 points but will have to skip the last two questions.

Hence, you are looking for a strategy that allows you to accumulate the maximum number of points possible by the end of the last question.

Intuition

To approach this problem, we need to think about each decision's consequences and explore different scenarios to come up with the optimal strategy. The essence of the problem has us consider two options for each question i: solving or skipping it.

When solving question i, we earn points[i] and skip the next brainpower[i] questions. If we skip it, we simply move on to making a decision on the following question.

A naive approach could involve trying all combinations of solving and skipping questions to find the optimal solution, but that would take an enormous amount of time for large arrays. Instead, we look for a Dynamic Programming (DP) approach that helps us store the results of subproblems to avoid redundant calculations.

The intuition behind the DP solution is to use recursion with memoization to keep track of the maximum points we can earn from any question i onward. At each question, we consider the maximum points of two scenarios: if we solve this question or if we skip it. We use a recursive function that takes an index i and returns the maximum points starting from question i. The base case is when we go beyond the last question, which earns us 0 points by default.

By caching the results of our recursive calls, we greatly reduce the number of calculations, since we ensure that each subproblem is solved exactly once. This makes the solution time-efficient enough to handle large input sizes.

Therefore, the @cache decorator above the recursive function (called dfs in the code) plays a critical role in memoizing previously computed results to speed up the recursive exploration. dfs(i) represents the maximum points we can earn starting from question i. We take the max between solving the current question and proceeding with dfs(i + brainpower[i] + 1) and skipping the current question with dfs(i + 1).

With this approach, we can ensure that we are considering every possible scenario and collecting the maximum points without exhaustively checking each combination, thereby arriving at an optimal solution.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution is implemented using a recursive function with memoization, two key elements that are often utilized in dynamic programming solutions.

Let's dissect the mostPoints function and the nested dfs function:

1. Dynamic Programming via Recursion: The dfs function embodies the concept of dynamic programming by breaking down the problem into smaller subproblems. At each step, we are essentially asking: "What's the maximum points I can get from this question onwards?" This leads to a recursive relation because the answer to this question depends on the maximum points from subsequent questions.

2. Memoization with @cache: The @cache decorator is a Python built-in decorator from the functools module that automatically saves the results of the dfs function calls into memory so that the next time the same function call is made with the same arguments, the cached result is returned immediately without recomputing. This feature helps in reducing the time complexity from exponential to polynomial.

3. Base Case: If i >= len(questions), the recursion stops (base case) and returns 0 because once we move past the last question, there are no more points to earn.

4. Recursive Case: At each question i, we consider two scenarios:

   • Solving the question: We earn points[i] and skip the next brainpower[i] questions. This is done by recursing with dfs(i + brainpower[i] + 1).
   • Skipping the question: We move to the next question by calling dfs(i + 1) without earning any points.

   We take the max between these two scenarios. The call to dfs(i + b + 1) represents the path where we solve the current question and dfs(i + 1) represents the path where we skip it.

5. Recursion Stack: Recursion uses a stack implicitly where each recursive call adds a frame to the stack. Once a call finishes, it is removed from the stack and the function returns to the previous call. This means we explore each branch (solve or skip) one at a time while maintaining only the current path in the stack, which is a depth-first search pattern.

6. Starting the Recursion: After defining the dfs function, we initiate the recursion by calling dfs(0), which evaluates the maximum points starting from the first question.

By combining these elements we arrive at an efficient solution that systematically explores each decision's consequences and appropriately tabulates them to avoid unnecessary re-computation. The result is that the first call to dfs(0) will eventually give us the maximum score we can achieve from the exam.

Example Walkthrough

Let's illustrate the solution approach with a small example. Given the array questions = [[2, 1], [3, 1], [5, 2]], let's walk through the dynamic programming steps to find the maximum points:

1. Call dfs(0) to start the recursion with the first question.

2. Compute dfs(0):

   • Solving question 0:
     • Earn 2 points and move to dfs(0 + brainpower[0] + 1) which is dfs(2).
     • Now compute dfs(2):
       • Solving question 2:
         • Earn 5 points. There's no question 3, so dfs(2 + brainpower[2] + 1) is dfs(5) which returns 0 (base case).
         • The total score for this path is 2 + 5 = 7.
       • Skipping question 2:
         • Move to dfs(3) which also returns 0 (base case).
         • The total score for this path remains 2 points.
     • Take the max for dfs(2) which is 7 points (solving question 2).
     • The total score for solving question 0 is 7 points.
   • Skipping question 0:
     • Move to dfs(0 + 1) which is dfs(1).
     • Now compute dfs(1):
       • Solving question 1:
         • Earn 3 points and move to dfs(1 + brainpower[1] + 1) which is dfs(3) and returns 0.
         • The total score for this path is 3 points.
       • Skipping question 1:
         • Move to dfs(2) which, as already computed, gives 5 points.
         • The total score for this path is 5 points.
     • Take the max for dfs(1) which is 5 points (skipping question 1).
     • The total score for skipping question 0 is 5 points.

3. Take the max between solving (dfs(0) = 7) and skipping (dfs(0) = 5) the first question, which is 7 points.

4. The recursive calls, leveraging memoization, ensure that dfs(2) is not recomputed when accessed through different paths.

At the end of this process, dfs(0) returns the answer, which is 7 points - the maximum number of points we can earn for this set of questions by optimally choosing whether to solve or skip each of them.

Solution Implementation

Time and Space Complexity

The given Python function mostPoints uses memoization (@cache) to optimize the recursive depth-first search (dfs) function to solve a dynamic programming problem. It involves making a decision at each question whether to solve it or to skip to the next one.

Time Complexity

The time complexity of the code primarily depends on two factors:

1. The number of subproblems to solve, which is O(n), where n is the number of questions.
2. The computation done for each subproblem, which is in this case O(1) since we are only making a choice between two options: solving the current question and jumping to the one after the bonus, or moving to the next question directly.

Each state of the dfs function is uniquely defined by the index i of the current question, and since each question gives us two choices, in the worst case, the function could be called for every index from 0 to n-1. However, due to memoization, each state is only computed once, and subsequent calls for the same state i return the cached result.

Therefore, the time complexity is O(n).

Space Complexity

The space complexity is determined by:

1. The space used by the recursion stack, which, in the worst case, could be O(n) if we go question by question without jumping through bonuses.
2. The space used by the memoization cache, which stores a result for each subproblem, resulting in O(n) space.

Since these two factors are additive, the total space complexity is O(n) as well. Each question index i is visited only once due to caching, which stores a constant amount of information (the maximum points from that question to the end).

In conclusion, both the time complexity and the space complexity of the mostPoints function are O(n).

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