Problem Informations

• Problem Index: 2140
• Problem Link: Solving Questions With Brainpower
• Topics: Array, Dynamic Programming

Problem Description

You are given a 0-indexed 2D integer array questions where $questions[i] = [points_i, brainpower_i]$.

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 $points_i$ points but you will be unable to solve each of the next $brainpower_i$ 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 \leq questions.length \leq 10^5$
• $questions[i].length == 2$
• $1 \leq points_i, brainpower_i \leq 10^5$

Intuition

The problem can be approached using dynamic programming. The core idea is to decide for each question whether to solve it or skip it, in a way that maximizes the total points gained. By leveraging the dynamic programming paradigm, we can systematically evaluate the potential outcomes at each step in reverse order.

Approach

To solve this problem, we adopt a dynamic programming approach where we define a DP array dp, where dp[i] represents the maximum points that can be obtained starting from question i.

1. Initialization: We initialize the DP array such that dp[i] = 0 for all i initially, except for the last question which is set to its own point value because there are no subsequent questions to influence its decision.

2. Reverse Iteration: We iterate over the questions in reverse order, from second-to-last to the first question. This reverse order allows us to decide the best strategy for each question based on optimal decisions made for subsequent questions.

3. Decision Making: For each question i:

   • We start by assuming we skip it, thereby inheriting the maximum points from the next question: dp[i] = dp[i + 1].
   • If we choose to solve the current question, we gain questions[i][0] points. After solving, we must skip the next questions[i][1] questions. Therefore, our points would become questions[i][0] + dp[i + questions[i][1] + 1] if staying within bounds.
   • We then update dp[i] to the maximum of solving or skipping the question: dp[i] = max(dp[i], questions[i][0] + future_points), where future_points is dp[i + questions[i][1] + 1] if the index is valid, otherwise 0.

4. Result Extraction: After processing all questions, dp[0] will contain the maximum points obtainable starting from the first question, which is the desired result.

This approach efficiently computes the solution in $O(n)$ time complexity, where $n$ is the number of questions, making it suitable for large inputs as defined in the problem constraints.

Code

C++

class Solution {
public:
    // Function to return the maximum of two numbers
    long long max(long long a, long long b) { 
        return a > b ? a : b; 
    }

    // Function to calculate the most points that can be earned
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();  // Get the number of questions
        vector<long long> dp(n, 0);  // DP array to store the maximum points at each question

        // Base case: the maximum points for the last question is itself
        dp[n-1] = questions[n-1][0];

        // Iterate through the questions in reverse order
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = dp[i + 1];  // Initially assume skipping the current question

            // Check if solving the current question provides more points
            if (i + questions[i][1] + 1 < n) {
                dp[i] = max(dp[i], questions[i][0] + dp[i + questions[i][1] + 1]);
            } else {
                dp[i] = max(dp[i], questions[i][0]);
            }
        }

        // The answer is the maximum points we can earn from the first question
        return dp[0];
    }
};

Python

class Solution:
    # Function to return the maximum of two numbers
    def max(self, a, b):
        return a if a > b else b

    # Function to calculate the most points that can be earned
    def mostPoints(self, questions):
        n = len(questions)  # Get the number of questions
        dp = [0] * n  # DP array to store the maximum points at each question

        # Base case: the maximum points for the last question is itself
        dp[n - 1] = questions[n - 1][0]

        # Iterate through the questions in reverse order
        for i in range(n - 2, -1, -1):
            dp[i] = dp[i + 1]  # Initially assume skipping the current question

            # Check if solving the current question provides more points
            if i + questions[i][1] + 1 < n:
                dp[i] = self.max(dp[i], questions[i][0] + dp[i + questions[i][1] + 1])
            else:
                dp[i] = self.max(dp[i], questions[i][0])

        # The answer is the maximum points we can earn from the first question
        return dp[0]

Complexity

• Time complexity: $O(n)$
  The time complexity is $O(n)$ because the algorithm iterates over the list of questions in reverse order exactly once, performing a constant number of operations for each question. This results in a linear relationship with respect to the number of questions $n$.
• Space complexity: $O(n)$
  The space complexity is $O(n)$ because we use a dynamic programming array dp to store the maximum points that can be earned starting from each question. This array has a length equal to the number of questions, $n$, thus resulting in a linear space requirement.