Description

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.

 

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 <= 105

• questions[i].length == 2

• 1 <= pointsi, brainpoweri <= 105

Thinking

Yet another Dynamic programming problem. Pretty similar to the knapsack problem. Still, the most important step: subproblem definition. Normally, what the problem asked is what we define the meaning of dp[i]. So here, we define dp[i] as the maximum points we can earn for the exam in the scope of [i to n-1].

According to the given example,

If question 0 is solved, you will earn 3 points but not be able to solve question 1 and 2.

we can know that whenever we got a point, there are two options, we either skip or not skip it. Since we want the max result, we need to compare the result in both direction.

If not skipping, dp[i] is at least equal to question[i][0], if i+question[i][1]+1 < n, then dp[i] = question[i][0] + dp[i+question[i][1] + 1]. If skipping, dp[i] = dp[i+1]. At last, dp[i] = max(dp[i], dp[i+1]).

Bottom-up approach (iterative)

​x
class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();

        vector<long long> dp(n+1, 0);

        dp[n] = 0;
        for(int i=n-1; i>=0; --i) {
            // Not Skip
            dp[i] = questions[i][0]; 

            // Skip and add
            if(i + questions[i][1] + 1 <= n) 
                dp[i] += dp[i+questions[i][1]+1];

            // If skip, that is dp[i+1]
            dp[i] = max(dp[i], dp[i+1]);
    
        }

        return dp[0];
    }
};

Top-down approach (recursive)

x
class Solution {
public:
    long long recur(vector<vector<int>>& questions, int i, vector<long long>& memo) {
        if(i >= questions.size()) return 0;
        
        // Check if this is already calced
        if(memo[i] != -1) return memo[i];

        int steps = i + questions[i][1] + 1;

        memo[i] = max(questions[i][0] + recur(questions, steps, memo), recur(questions, i+1, memo));

        return memo[i];
    }

    long long mostPoints(vector<vector<int>>& questions) {
        vector<long long> memo(questions.size(), -1);
        return recur(questions, 0, memo);
    }
};

The memo is the memoization method. Normally, the memo is viewed some kind of telephone book for recursion. But here it is more like the dp[] array in iterative approach.