2140. Solving Questions With Brainpower
Description
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 earn3
points but you will be unable to solve questions1
and2
. - If instead, question
0
is skipped and question1
is solved, you will earn4
points but you will be unable to solve questions2
and3
.
- If question
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
Solutions
Solution 1: Memoization Search
We design a function $dfs(i)$, which represents the maximum score that can be obtained starting from the $i$-th problem. Therefore, the answer is $dfs(0)$.
The calculation method of the function $dfs(i)$ is as follows:
- If $i \geq n$, it means that all problems have been solved, return $0$;
- Otherwise, let the score of the $i$-th problem be $p$, and the number of problems to skip be $b$, then $dfs(i) = \max(p + dfs(i + b + 1), dfs(i + 1))$.
To avoid repeated calculations, we can use the method of memoization search, using an array $f$ to record the values of all already computed $dfs(i)$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of problems.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Solution 2: Dynamic Programming
We define $f[i]$ as the maximum score that can be obtained starting from the $i$-th problem. Therefore, the answer is $f[0]$.
Considering $f[i]$, let the score of the $i$-th problem be $p$, and the number of problems to skip be $b$. If we solve the $i$-th problem, then we need to solve the problem after skipping $b$ problems, thus $f[i] = p + f[i + b + 1]$. If we skip the $i$-th problem, then we start solving from the $(i + 1)$-th problem, thus $f[i] = f[i + 1]$. We take the maximum value of the two. The state transition equation is as follows:
$$ f[i] = \max(p + f[i + b + 1], f[i + 1]) $$
We calculate the values of $f$ from back to front, and finally return $f[0]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of problems.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 |
|