Solving Questions With Brainpower
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 (from the first to the last question). For each question i, you can either:
- Solve it and earn
pointsipoints — but you will be unable to solve the nextbrainpoweriquestions (i.e., the nextbrainpoweriquestions are skipped). - Skip it and proceed to the next question.
Return the maximum points you can earn for the exam.
Examples
Input: [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Input: [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Hints
Consider using dynamic programming to store the maximum points achievable starting from each question.
Define `dp[i]` as the maximum points you can earn starting from question `i`. How can you express `dp[i]` in terms of `dp[i + brainpower[i] + 1]` and `dp[i + 1]`?
The recurrence relation is `dp[i] = max(questions[i][0] + dp[i + questions[i][1] + 1], dp[i + 1])`. How would you handle the base case when `i` exceeds the array bounds?
Related Problems
Solving Questions With Brainpower
You are given a 0-indexed 2D integer array `questions` where `questions[i] = [pointsi, brainpoweri]`.