# Leetcode 2140: Solving Questions With Brainpower

--

In this problem, we are trying to find a testing strategy to optimize the number of points in a test giving the following rules:

You are given a

0-indexed2D 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 tosolveorskipeach question. Solving question`i`

willearnyou`pointsi`

points but you will beunableto 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

`0`

is solved, you will earn`3`

points but you will be unable to solve questions`1`

and`2`

. If instead, question`0`

is skipped and question`1`

is solved, you will earn`4`

points but you will be unable to solve questions`2`

and`3`

.

Returnthemaximumpoints you can earn for the exam.

To solve this problem, I simply memoized the following result in a array `r`

. where `r[i]`

is the maximum number of points we can obtain if we start the test at index `i`

.

There are fundamentally 2 possibility for the value of `r[i]`

, if we decide to solve the problem `i`

and get the points, then the maximum number of points we will get will be `pointsi + r[i + brainpoweri + 1]`

(if `i + brainpoweri + 1`

is actually a valid index, `0`

otherwise). The other possibility is not to solve the problem `i`

, in that case the best score we can get is `r[i+1]`

. We then take the max of the 2 values to obtain the best possible score for `r[i]`

.

Since the value of `r[i]`

depends of others `r[j]`

values with `j > i`

, we can compute the values of `r`

going in reverse order from `n-1`

to `0`

. At the end we simply return `r[0]`

.

This is the algorithm idea:

This is the code I obtained in C++:

`class Solution {`

public:

long long mostPoints(vector<vector<int>>& questions) {

int n = questions.size();

long long* r = new long long[n];

for (int i = n - 1; i >= 0; i--) {

int b = questions.at(i).at(1);

int p = questions.at(i).at(0);

if (i == n - 1) {

r[i] = p;

} else if (i + b + 1 >= n) {

r[i] = r[i+1];

if (p > r[i]) {

r[i] = p;

}

} else {

r[i] = r[i+1];

if (r[i] < p + r[i + b + 1]) {

r[i] = p + r[i + b + 1];

}

}

}

// cout << "[";

// for (int i = 0; i < n; i++) {

// cout << r[i] << ", ";

// }

// cout << "]";

return r[0];

}

};

Happy coding :)