Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

At each question, either skip it and keep the next question available, or earn its points and jump past its required cooldown. Both choices leave a suffix of the same problem, so suffix dynamic programming compares their best future totals.

Approach

Let dp[i] be the maximum points obtainable starting at question i. Fill it backward. Taking the question earns its points plus dp[i + brainpower + 1] when that index exists; skipping earns dp[i + 1]. Store the larger value. A jump beyond the array has no remaining reward. Initialize the last question's value from its positive points and return dp[0].

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        dp = [0] * n
        dp[n - 1] = questions[n - 1][0]

        for i in range(n - 2, -1, -1):
            points = questions[i][0]
            brainpower = questions[i][1]

            dp[i] = points
            if i + brainpower + 1 < n:
                dp[i] += dp[i + brainpower + 1]
            
            dp[i] = max(dp[i], dp[i + 1])
        
        return dp[0]

Complexity analysis

Let n = questions.length. Time: O(n). Auxiliary space: O(n) for the one-dimensional DP table.