Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2140.html
2140. Solving Questions With Brainpower (Medium)
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
0is solved, you will earn3points but you will be unable to solve questions1and2. - If instead, question
0is skipped and question1is solved, you will earn4points but you will be unable to solve questions2and3.
- 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 <= 105questions[i].length == 21 <= pointsi, brainpoweri <= 105
Related Topics:
Array, Dynamic Programming
Similar Questions:
Solution 1. DP
// OJ: https://leetcode.com/problems/solving-questions-with-brainpower/
// Time: O(N)
// Space: O(N)
class Solution {
public:
long long mostPoints(vector<vector<int>>& A) {
long long N = A.size();
vector<long long> dp(N + 2);
for (int i = 0; i < N; ++i) {
int next = i + A[i][1] + 2;
if (next > N) next = N + 1;
dp[i + 1] = max(dp[i + 1], dp[i]);
dp[next] = max(dp[next], dp[i + 1] + A[i][0]);
}
return *max_element(begin(dp), end(dp));
}
};