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:

Algorithm ideas

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 :)