# 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-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 `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`.
Return the maximum points 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 :)