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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4
5
6
7
8

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 <= 10^5
  • questions[i].length == 2
  • 1 <= pointsi, brainpoweri <= 10^5

Solution

Method 1 - Using Dynamic Programming

This problem can be solved using Dynamic Programming since it requires breaking the problem into overlapping subproblems optimally. We start at the first question and make two choices:

  1. Solve the question: Add its points to the answer and skip the next brainpower questions.
  2. Skip the question: Move to the next question directly.

The goal is to find the maximum points that can be accumulated. We’ll use a bottom-up DP approach with an auxiliary array where dp[i] represents the maximum points achievable starting from question i.

Here is the approach:

  1. Define dp[i] where dp[i] represents the max points achievable starting from question i.
  2. Compute dp[i] as the maximum of:
    • questions[i][0] (points for solving the question) + dp[i + questions[i][1] + 1] (skip brainpower questions after solving).
    • dp[i + 1] (next max points if we skip the question).
  3. Start calculating dp values for each question from the last index to the first.
  4. Return dp[0] as the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n];
        long ans = 0;

        for (int i = n - 1; i >= 0; i--) {
            int points = questions[i][0];
            int brainpower = questions[i][1];
            int skipTo = i + brainpower + 1;
            long solve = points + (skipTo < n ? dp[skipTo] : 0);
            long skip = (i + 1 < n ? dp[i + 1] : 0);
            dp[i] = Math.max(solve, skip);
        }

        return dp[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n: int = len(questions)
        dp: List[int] = [0] * n
        ans: int = 0
        
        for i in range(n - 1, -1, -1):
            points, brainpower = questions[i]
            skip_to: int = i + brainpower + 1
            solve: int = points + (dp[skip_to] if skip_to < n else 0)
            skip: int = dp[i + 1] if i + 1 < n else 0
            dp[i] = max(solve, skip)
        
        return dp[0]

Complexity

  • ⏰ Time complexity: O(n) where n is the number of questions (since we compute dp[i] for all i).
  • 🧺 Space complexity: O(n) for the dp array.