Problem Statement:

You are given a 0-indexed 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 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.

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⁵
questions[i].length == 2
1 <= points_i, brainpower_i <= 10⁵

Solution:

For ease of understanding, let us start with a baseline solution which uses recursion. It fails for heavy test cases but still passes for toy tests given in problem description. The logic is simple: We can either choose to solve the current question and accumulate its points (and then skip the next few) or skip the current question. The answer is the maximum of both cases.

 
class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions, int start=0)
    {
        if (start>=questions.size()) return 0;
        int points = questions[start][0], skips = questions[start][1];
        int a = points + mostPoints(questions, start+skips+1);
        int b = mostPoints(questions, start+1);
        return max(a,b);
    }
};

To pass larger tests, we will need to add memoization. Notice that we may be doing repititive calculation in baseline solution. So, to avoid that we simple store the solutions in an array memo and check this array everytime and return from memo without doing calculation whenever possible. Let us also use long long dtype for memo.

 
class Solution {
    vector<long long> memo;
public:
    long long mostPoints(vector<vector<int>>& questions, int start=0)
    {
        if (start>=questions.size()) return 0;
        if (start==0){memo = vector<long long>(questions.size(),-1);}
        if (memo[start]!=-1) return memo[start];
        int points = questions[start][0], skips = questions[start][1];
        long long a = (long long)points + mostPoints(questions, start+skips+1);
        long long b = mostPoints(questions, start+1);
        return memo[start] = max(a,b);
    }
};

This gives us an AC with flying colors. \uD83D\uDE80

We can also use bottom-up DP to solve this problem. For this we start with an array filled with zeroes and traverse the questions array in reverse. While traversal, we use the same logic of maximum of taking points + skipping or not taking each entry.

 
class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) 
    {
        int n = questions.size();
        vector<long long> dp(n);
        for (int i=n-1; i>=0; i--)
        {
            int points = questions[i][0], skips = questions[i][1];
            long long a = (i+skips+1<n)?dp[i+skips+1]:0;
            long long b = (i+1<n)?dp[i+1]:0;
            dp[i] = max(a+points, b);
        }
        return dp[0];
    }
};

This also gives us AC. Now, if you are a java kind of person, here is the java version of the last solution.

 
class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long dp[] = new long[n];
        for(int i=n-1; i>=0; i--)
        {
            int points = questions[i][0], skips = questions[i][1];
            long a = (i+skips+1<n)?dp[i+skips+1]:0;
            long b = (i+1<n)?dp[i+1]:0;
            dp[i] = Math.max(a+(long)points, b);
        }
        return dp[0];
    }
}

To write the memoized recursion solution in java, I will need to write a separate helper function as passing start=0 in argument is not possible in java (ref), so hopefully you can do that yourself.

Complexity: TC and SC of all solutions is $O(n)$.

\uD83D\uDE80Upvote\uD83D\uDE80 if you liked my post.