2140: Solving-Questions-With-Brainpower
Medium

New month, new me.

This question talks like a dynamic programming question. Basically, we will keep a dp array, that intends on tracking the maximum points you can have at a specific index, while being fit to solve the current question.

At each index, we check if dp[index] = max(dp[index], dp[index-1]), since we want to make sure that we start with the maximum number of points possible, and then updating the value present at min((long long)questions.size(), i+brainpower+1) if dp[index]+points is larger greater than the value present at that index.

Then, we just keep repeating this for every question, and then simply return the value at the end of dp, as it should be the maximum points you can earn for the exam.

code

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        vector<long long> dp (questions.size()+1, 0);
        for (int i = 0; i < questions.size(); ++i) {
            long long points = questions[i][0];
            long long brainpower = questions[i][1];
            
            if (i > 0) dp[i] = max(dp[i], dp[i-1]);
            dp[min((long long)questions.size(), i+brainpower+1)] = max(dp[min((long long)questions.size(), i+brainpower+1)], dp[i]+points);
        }
        return max(dp.back(), dp[questions.size()-1]);
    }
};

complexity