Welcome to Subscribe On Youtube
2140. Solving Questions With Brainpower
Description
You are given a 0indexed 2D integer array questions
where questions[i] = [points_{i}, brainpower_{i}]
.
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 points_{i}
points but you will be unable to solve each of the next brainpower_{i}
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
0
is solved, you will earn3
points but you will be unable to solve questions1
and2
.  If instead, question
0
is skipped and question1
is solved, you will earn4
points but you will be unable to solve questions2
and3
.
 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 <= 10^{5}
questions[i].length == 2
1 <= points_{i}, brainpower_{i} <= 10^{5}
Solutions

class Solution { private int n; private Long[] f; private int[][] questions; public long mostPoints(int[][] questions) { n = questions.length; f = new Long[n]; this.questions = questions; return dfs(0); } private long dfs(int i) { if (i >= n) { return 0; } if (f[i] != null) { return f[i]; } int p = questions[i][0], b = questions[i][1]; return f[i] = Math.max(p + dfs(i + b + 1), dfs(i + 1)); } }

class Solution { public: long long mostPoints(vector<vector<int>>& questions) { int n = questions.size(); long long f[n]; memset(f, 0, sizeof(f)); function<long long(int)> dfs = [&](int i) > long long { if (i >= n) { return 0; } if (f[i]) { return f[i]; } int p = questions[i][0], b = questions[i][1]; return f[i] = max(p + dfs(i + b + 1), dfs(i + 1)); }; return dfs(0); } };

class Solution: def mostPoints(self, questions: List[List[int]]) > int: @cache def dfs(i: int) > int: if i >= len(questions): return 0 p, b = questions[i] return max(p + dfs(i + b + 1), dfs(i + 1)) return dfs(0)

func mostPoints(questions [][]int) int64 { n := len(questions) f := make([]int64, n) var dfs func(int) int64 dfs = func(i int) int64 { if i >= n { return 0 } if f[i] > 0 { return f[i] } p, b := questions[i][0], questions[i][1] f[i] = max(int64(p)+dfs(i+b+1), dfs(i+1)) return f[i] } return dfs(0) }

function mostPoints(questions: number[][]): number { const n = questions.length; const f = Array(n).fill(0); const dfs = (i: number): number => { if (i >= n) { return 0; } if (f[i] > 0) { return f[i]; } const [p, b] = questions[i]; return (f[i] = Math.max(p + dfs(i + b + 1), dfs(i + 1))); }; return dfs(0); }