#2140

Solving Questions With Brainpower

specialist · 705 · lc medium +30 · verified · 60.2% accepted · 2,949 likes · top 59%

⚑ Linear 1D DP

Description

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

The array describes an exam where you must consider each question in order and decide whether to solve it or skip it. Solving question i earns you pointsi points but forces you to skip the next brainpoweri questions. Skipping a question lets you proceed to the next one.

 - For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:

 - Solving question 0 earns 3 points but you cannot attempt questions 1 or 2.

 - Alternatively, skipping question 0 and solving question 1 earns 4 points but skips questions 2 and 3.

Return the maximum points you can earn on 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.

Code

1
2
3