Solution Explanation: Solving Questions With Brainpower

This problem asks to find the maximum points achievable by solving questions in a given order, with the constraint that solving a question prevents solving a certain number of subsequent questions. Two approaches effectively solve this: Memoization (top-down dynamic programming) and Dynamic Programming (bottom-up).

Approach 1: Memoization (Top-Down Dynamic Programming)

This approach uses recursion with memoization to avoid redundant calculations. The core idea is a recursive function dfs(i) that calculates the maximum points achievable starting from question i.

Logic:

1. Base Case: If i is beyond the last question, no more points can be earned, so return 0.
2. Memoization Check: If the result for i is already computed (stored in f[i]), return the stored value.
3. Recursive Step: Consider two options for question i:
   • Solve: Earn points[i] points, but skip the next brainpower[i] questions. Recursively call dfs(i + brainpower[i] + 1) to find the maximum points from the remaining questions.
   • Skip: Skip question i and recursively call dfs(i + 1) to find the maximum points from the next question.
4. Return the maximum: Return the maximum of the "solve" and "skip" options. Store the result in f[i] for memoization.

Time Complexity: O(n), where n is the number of questions. Each question is processed at most once. Space Complexity: O(n) due to the memoization array f. The recursive call stack might also consume space in the worst case, but this is usually bounded by n.

Approach 2: Dynamic Programming (Bottom-Up)

This approach iteratively builds a solution from the end to the beginning, avoiding recursion. f[i] stores the maximum points achievable starting from question i.

Logic:

1. Initialization: Initialize f[n] to 0 (no points from beyond the last question).
2. Iteration: Iterate through questions from the last question (n-1) to the first question (0).
3. State Transition: For each question i, consider two options:
   • Solve: If solving i doesn't go beyond the array, earn points[i] points, add the maximum achievable points from i + brainpower[i] + 1 (obtained from f[i + brainpower[i] + 1]).
   • Skip: The maximum points achievable are the same as starting from the next question (f[i + 1]).
4. Update: Assign the maximum of the two options to f[i].
5. Result: f[0] contains the maximum points achievable starting from the first question.

Time Complexity: O(n), as each question is processed once. Space Complexity: O(n) to store the f array.

Code Examples (Python)

Memoization:

from functools import cache
 
def mostPoints(questions: List[List[int]]) -> int:
    @cache
    def dfs(i: int) -> int:
        if i >= len(questions):
            return 0
        p, b = questions[i]
        return max(p + dfs(i + b + 1), dfs(i + 1))
    return dfs(0)

Dynamic Programming:

def mostPoints(questions: List[List[int]]) -> int:
    n = len(questions)
    f = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        p, b = questions[i]
        j = i + b + 1
        f[i] = max(f[i + 1], p + (0 if j > n else f[j]))
    return f[0]

Both approaches provide the same correct result with the same time and space complexities. The dynamic programming approach is often slightly more efficient in practice due to the elimination of recursive function calls. Choose the approach that best suits your understanding and coding style.