Solving Questions With Brainpower

Leetcode Problem:

• Solving Questions With Brainpower

Summary

• Given a 2D array of questions where each question has a point value and a brainpower value, find the maximum points that can be earned by solving the questions in order.

Approach

• Dynamic Programming: The problem can be solved using dynamic programming
• The idea is to maintain a memoization table to store the maximum points that can be earned for each question
• The function iterates over the questions in reverse order and for each question, it calculates the maximum points that can be earned by either solving the current question or skipping it.

Complexity

• O(N) where N is the number of questions, as each question is visited once.

Solution Code:

class Solution {
public:
    long long memo[200001] = {0};
    long long mostPoints(vector>& questions) {
        int N = questions.size();
        for(int i = N - 1; i >= 0; i--){
            int point = questions[i][0];
            int brainpower = questions[i][1];
            memo[i] = max(point + memo[i + brainpower + 1], memo[i+1]);
        }
        return memo[0];
    }
};