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 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. Return the maximum points you can earn for the exam.
Key Insights
- You must process questions in the given order.
- Choosing to solve a question affects the subsequent questions you can solve due to the brainpower cost.
- Dynamic programming is a suitable approach to keep track of the maximum points earned up to each question.
- The decision to solve or skip a question depends on the cumulative points from previous questions and the brainpower cost of solved questions.
Space and Time Complexity
Time Complexity: O(n), where n is the number of questions, since we traverse the list once. Space Complexity: O(1), since we only need a few variables to store the current maximum points and the index.
Solution
We use a dynamic programming approach to solve this problem. The core idea is to maintain a running total of the maximum points that can be earned as we process each question. We will iterate through the list of questions and, for each question, decide whether to solve it (adding points) or skip it (moving to the next question). If we solve a question, we must skip subsequent questions based on the brainpower cost associated with that question. We keep track of the maximum points earned at each step using a variable.