# Solving Questions With Brainpower
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/solving-questions-with-brainpower)
Canonical: https://scaleengineer.com/dsa/problems/solving-questions-with-brainpower
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** 2D integer array `questions` where `questions[i] = [pointsi, brainpoweri]`.

The array describes the questions of an exam, where you have to process the questions **in order** (i.e., starting from question `0`) and make a decision whether to **solve** or **skip** each question. Solving question `i` will **earn** you `pointsi` points but you will be **unable** to solve each of the next `brainpoweri` questions. If you skip question `i`, you get to make the decision on the next question.

* For example, given `questions = [[3, 2], [4, 3], [4, 4], [2, 5]]`:  
  * If question `0` is solved, you will earn `3` points but you will be unable to solve questions `1` and `2`.
  * If instead, question `0` is skipped and question `1` is solved, you will earn `4` points but you will be unable to solve questions `2` and `3`.

Return _the **maximum** points you can earn for the exam_.

**Example 1:**

**Input:** questions = [[3,2],[4,3],[4,4],[2,5]]
**Output:** 5
**Explanation:** The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

**Example 2:**

**Input:** questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
**Output:** 7
**Explanation:** The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

**Constraints:**

* `1 <= questions.length <= 105`
* `questions[i].length == 2`
* `1 <= pointsi, brainpoweri <= 105`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's choices into a recursive function. For each question, we explore two paths: solving it or skipping it. The function calculates the maximum points for each path by making recursive calls and returns the greater of the two. This method is intuitive but highly inefficient as it re-computes solutions for the same subproblems multiple times.
**Time:** O(2^n), where n is the number of questions. For each question, the function branches into two recursive calls, leading to an exponential number of computations. · **Space:** O(n), where n is the number of questions. This is due to the maximum depth of the recursion stack, which can occur if we skip every question.
**Pros:** Simple to understand and implement as it directly models the decision-making process at each step.
**Cons:** Extremely inefficient due to the exponential number of redundant calculations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms for the given constraints.
### Explanation
We define a recursive function, let's call it `solve(index)`, which calculates the maximum points obtainable from `questions[index]` onwards.

*   **Base Case**: If `index` is out of bounds (i.e., `index >= questions.length`), it means there are no more questions to consider, so we return 0 points.
*   **Recursive Step**: For the current question at `index`, we have two choices:
    1.  **Solve**: We gain `questions[index][0]` points. We then have to skip the next `questions[index][1]` questions. The next question we can consider is at `index + questions[index][1] + 1`. The total points for this choice would be `questions[index][0] + solve(index + questions[index][1] + 1)`.
    2.  **Skip**: We gain 0 points for the current question and move to the next one at `index + 1`. The total points for this choice would be `solve(index + 1)`.

The function returns the maximum of the points from these two choices. The initial call to start the process is `solve(0)`.

```java
class Solution {
    public long mostPoints(int[][] questions) {
        return solve(0, questions);
    }

    private long solve(int i, int[][] questions) {
        // Base case: If we are past the last question, we can't earn more points.
        if (i >= questions.length) {
            return 0;
        }

        // Option 1: Solve the current question
        // We get points for this question and jump ahead by brainpower[i] + 1.
        int points = questions[i][0];
        int brainpower = questions[i][1];
        long pointsIfSolved = points + solve(i + brainpower + 1, questions);

        // Option 2: Skip the current question
        // We get 0 points for this question and move to the next one.
        long pointsIfSkipped = solve(i + 1, questions);

        // Return the maximum of the two options.
        return Math.max(pointsIfSolved, pointsIfSkipped);
    }
}
```
### Algorithm
*   Define a recursive function `solve(i)` that computes the maximum points starting from question `i`.
*   **Base Case:** If `i` is greater than or equal to the number of questions `n`, it means we are past the last question, so we return 0 points.
*   **Recursive Step:** For question `i`, we have two choices:
    1.  **Solve:** Earn `questions[i][0]` points and recursively call the function for the next available question at index `i + questions[i][1] + 1`.
    2.  **Skip:** Earn 0 points for the current question and recursively call the function for the next question at index `i + 1`.
*   The function returns the maximum value between the 'solve' and 'skip' options.
*   The initial call is `solve(0)`.

## Top-Down Dynamic Programming (Memoization)
This approach enhances the brute-force recursion by using memoization, a top-down dynamic programming technique. It avoids re-calculating results for the same subproblems by storing them in a memoization table (e.g., an array). When the function is called for a particular question index, it first checks if the result is already stored. If so, it returns the stored value; otherwise, it computes the result, stores it, and then returns it. This drastically reduces the computation time from exponential to linear.
**Time:** O(n). Each state `solve(i)` for `i` from 0 to `n-1` is computed only once. The work inside each function call is constant time. · **Space:** O(n). We use an array of size `n` for memoization, and the recursion stack can also go up to depth `n`.
**Pros:** Drastically improves time complexity to linear.; Guarantees that each subproblem is solved only once.; Maintains the intuitive recursive structure of the problem.
**Cons:** The recursion depth can be large, potentially leading to a `StackOverflowError` for very deep recursion chains, though modern platforms often have large stack sizes.; Slightly more memory usage than the bottom-up approach due to the recursion stack.
### Explanation
We use the same recursive structure as the brute-force approach but add a cache (memoization array) to store the results of subproblems.

We introduce a memoization table, an array `memo` of size `n`, to store the result of `solve(index)`. This array is initialized with a sentinel value (e.g., -1) to mark states that haven't been computed.

Inside the `solve(index)` function:
1.  We first check the base case: if `index >= n`, return 0.
2.  Then, we check our cache: if `memo[index]` is not -1, we return the stored value immediately, avoiding re-computation.
3.  If the value is not cached, we perform the same logic as the brute-force approach: calculate the maximum points from either solving or skipping the current question.
4.  Before returning the result, we store it in `memo[index]` so it can be reused later.

```java
import java.util.Arrays;

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] memo = new long[n];
        // Initialize memo with a value to indicate not computed
        Arrays.fill(memo, -1);
        return solve(0, questions, memo);
    }

    private long solve(int i, int[][] questions, long[] memo) {
        // Base case
        if (i >= questions.length) {
            return 0;
        }
        // If already computed, return stored value
        if (memo[i] != -1) {
            return memo[i];
        }

        // Option 1: Solve the current question
        int points = questions[i][0];
        int brainpower = questions[i][1];
        long pointsIfSolved = points + solve(i + brainpower + 1, questions, memo);

        // Option 2: Skip the current question
        long pointsIfSkipped = solve(i + 1, questions, memo);

        // Store the result in memo and return
        memo[i] = Math.max(pointsIfSolved, pointsIfSkipped);
        return memo[i];
    }
}
```
### Algorithm
*   Create a memoization array `memo` of size `n` (number of questions), initialized with a value like -1 to indicate that a state has not been computed.
*   Define a recursive function `solve(i, memo)`.
*   **Base Case:** If `i >= n`, return 0.
*   **Memoization Check:** If `memo[i]` is not -1, it means the result for this index is already computed, so return `memo[i]`.
*   **Recursive Step:** If the result is not in the memo table, calculate the points for solving and skipping as in the brute-force approach.
    *   `solve_points = questions[i][0] + solve(i + questions[i][1] + 1, memo)`
    *   `skip_points = solve(i + 1, memo)`
*   Store the computed maximum of `solve_points` and `skip_points` in `memo[i]` before returning it.
*   The initial call is `solve(0, memo)`.

## Bottom-Up Dynamic Programming (Tabulation)
This is an iterative, or bottom-up, approach to dynamic programming. Instead of using recursion, we build the solution from the base cases up. We use a DP array, say `dp`, where `dp[i]` stores the maximum points obtainable starting from question `i`. By iterating backwards from the end of the questions array, we ensure that when we calculate `dp[i]`, the values `dp[i+1]` (for skipping) and `dp[i + brainpower + 1]` (for solving) have already been computed. This approach is highly efficient and avoids the potential for stack overflow errors associated with deep recursion.
**Time:** O(n). We have a single loop that iterates `n` times, with constant time operations inside. · **Space:** O(n), for the DP array used to store the subproblem solutions.
**Pros:** Very efficient in both time and space, with the same asymptotic complexity as memoization.; Avoids recursion overhead and eliminates the risk of `StackOverflowError`.; Often slightly faster in practice than the memoized recursive solution.
**Cons:** Can be slightly less intuitive to formulate compared to the direct recursive translation (top-down approach).; Requires careful determination of the iteration order.
### Explanation
We define a DP array, `dp`, of size `n+1`, where `dp[i]` represents the maximum points we can earn from questions `i` to `n-1`. The extra element `dp[n]` serves as a convenient base case, representing 0 points since there are no questions left from index `n` onwards.

We iterate backwards from the second-to-last question (`i = n-1`) to the first question (`i = 0`). This reverse order is crucial because to calculate `dp[i]`, we need the values for future states (`dp[i+1]` and `dp[i + brainpower + 1]`), which will have already been computed.

**Iteration Logic**: For each `i` from `n-1` down to `0`:
1.  **Solve option**: The points are `questions[i][0]` plus the points from the next solvable question. The index of this next question is `i + questions[i][1] + 1`. We look up the pre-computed maximum points from that index, which is `dp[i + questions[i][1] + 1]`. We must handle the case where this index is out of bounds (`>= n`), in which case we add 0. A clean way is to use `dp[min(n, nextIndex)]`.
2.  **Skip option**: The points are simply the maximum points we can get from the next question onwards, which is already stored in `dp[i+1]`.
3.  We set `dp[i]` to the maximum of these two options.

The final answer is `dp[0]`, which represents the maximum points starting from the very first question.

```java
class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        // dp[i] will store the maximum points starting from question i.
        // We use size n+1 for a clean base case dp[n] = 0.
        long[] dp = new long[n + 1];

        // Iterate backwards from the last question.
        for (int i = n - 1; i >= 0; i--) {
            int points = questions[i][0];
            int brainpower = questions[i][1];

            // Option 1: Solve question i.
            // The next question we can solve is at index i + brainpower + 1.
            int nextIndex = i + brainpower + 1;
            long pointsIfSolved = points;
            if (nextIndex < n) {
                pointsIfSolved += dp[nextIndex];
            }

            // Option 2: Skip question i.
            // The points will be the same as if we started from question i+1.
            long pointsIfSkipped = dp[i + 1];

            // dp[i] is the maximum of the two options.
            dp[i] = Math.max(pointsIfSolved, pointsIfSkipped);
        }

        // The answer is the maximum points starting from question 0.
        return dp[0];
    }
}
```
### Algorithm
*   Let `n` be the number of questions.
*   Create a DP array `dp` of size `n + 1` and initialize it with 0s. `dp[i]` will store the maximum points obtainable from question `i` to the end.
*   `dp[n]` is the base case, representing 0 points as there are no questions left.
*   Iterate backwards from `i = n - 1` down to `0`.
*   For each `i`:
    *   Calculate points if we solve question `i`: `solve_points = questions[i][0] + dp[next_index]`, where `next_index = min(n, i + questions[i][1] + 1)`.
    *   Calculate points if we skip question `i`: `skip_points = dp[i + 1]`.
    *   Update the DP table: `dp[i] = max(solve_points, skip_points)`.
*   The final answer is `dp[0]`, which holds the maximum points starting from the first question.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  Long[] f;
private
  int[][] questions;
public
  long mostPoints(int[][] questions) {
    n = questions.length;
    f = new Long[n];
    this.questions = questions;
    return dfs(0);
  }
private
  long dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int p = questions[i][0], b = questions[i][1];
    return f[i] = Math.max(p + dfs(i + b + 1), dfs(i + 1));
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long mostPoints(vector<vector<int>> &questions) {
    int n = questions.size();
    long long f[n];
    memset(f, 0, sizeof(f));
    function<long long(int)> dfs = [&](int i) -> long long {
      if (i >= n) {
        return 0;
      }
      if (f[i]) {
        return f[i];
      }
      int p = questions[i][0], b = questions[i][1];
      return f[i] = max(p + dfs(i + b + 1), dfs(i + 1));
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def mostPoints(self, 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)

```