Solving Questions With Brainpower
Problem
For each question [points, brainpower], you may solve it (gaining points but skipping the next brainpower questions) or skip to the next. Maximize total points.
questions = [[3,2],[4,3],[4,4],[2,5]]5def most_points(questions):
n = len(questions)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
p, b = questions[i]
nxt = i + b + 1
take = p + (dp[nxt] if nxt <= n else 0)
skip = dp[i + 1]
dp[i] = max(take, skip)
return dp[0]function mostPoints(questions) {
const n = questions.length;
const dp = new Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; i--) {
const [p, b] = questions[i];
const nxt = i + b + 1;
const take = p + (nxt <= n ? dp[nxt] : 0);
const skip = dp[i + 1];
dp[i] = Math.max(take, skip);
}
return dp[0];
}class Solution {
public long mostPoints(int[][] questions) {
int n = questions.length;
long[] dp = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
int p = questions[i][0], b = questions[i][1];
int nxt = i + b + 1;
long take = p + (nxt <= n ? dp[nxt] : 0);
long skip = dp[i + 1];
dp[i] = Math.max(take, skip);
}
return dp[0];
}
}long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int p = questions[i][0], b = questions[i][1];
int nxt = i + b + 1;
long long take = p + (nxt <= n ? dp[nxt] : 0);
long long skip = dp[i + 1];
dp[i] = max(take, skip);
}
return dp[0];
}Explanation
At each question you have a clean either/or choice: solve it and earn its points but be forced to skip the next brainpower questions, or skip it and move on to the next. We want the maximum total points, and that screams dynamic programming.
The trick is to fill dp from right to left. Define dp[i] as the best score obtainable starting at question i. Then for each i we just compare the two choices and keep the larger.
If we solve question i we get p points and must jump to nxt = i + b + 1, so take = p + dp[nxt] (or just p if that jumps past the end). If we skip, skip = dp[i + 1]. Then dp[i] = max(take, skip).
Example: questions = [[3,2],[4,3],[4,4],[2,5]]. Solving q0 gives 3 and jumps to index 0+2+1 = 3, where q3 adds 2, for a total of 5 — better than any alternative, so the answer is 5.
Because each dp[i] only looks at already-computed entries to its right, one backward pass solves everything in O(n) time.