Solving Questions With Brainpower
MediumDynamic ProgrammingGreedy
Description
Given exam questions with points and brainpower (skip count after solving), maximize points by choosing which questions to solve. Return the result as an integer.
Examples
Input:
questions = [[3,2],[4,3],[4,4],[2,5]]Output:
5Explanation:
Using dynamic programming from right to left, dp[i] = max(skip question i, solve question i). Solving question i gives points[i] + dp[i + brainpower[i] + 1], since brainpower[i] questions must be skipped after solving. Solving q0 (3 points, skip 2) allows solving q3 (2 points), totaling 5.
Input:
questions = [[1,0]]Output:
1Explanation:
Minimal case with one question worth 1 point and 0 brainpower.
Input:
questions = [[5,1],[2,2],[3,1],[1,0]]Output:
8Explanation:
Take question 0 (5 points, skip 1), skip question 1, take question 2 (3 points, skip 1), skip question 3. Total: 5 + 3 = 8 points.
Constraints
- •
1 ≤ questions.length ≤ 10⁵