2140.Solving_Questions_With_Brainpower(Medium).md

2140. Solving Questions With Brainpower (Medium)

Date and Time: Apr 1, 2025

Link: https://leetcode.com/problems/solving-questions-with-brainpower

Edge Case 1:

Input: [[21,5],[92,3],[74,2],[39,4],[58,2],[5,5],[49,4],[65,3]]
Output: 157
Explanation: Take [92, 3] then take [65, 3]

Edge Case 2:

Input: [[3,2],[5,5]]
Output: 5

Walk-through:

Fill dp[] backward, each dp[i] is the maximum pts we can get from [i, n-1], and we update dp[i] = max(solve problem, skip problem).

solve_problem = dp[i] + dp[i+step+1], the total points we can get from current point and the next points we can get. If i+step+1 is out of bound, we set it to 0.

skip_problem = dp[i+1], if we don't take the current point, we must skip current problem, and the maximum points we can get will just be its right neighbor. Because we may skip multiple questions to the maximum point question, so each right neighbor represents the maximum pt that we can get. If i+1 < len(questions), we can take the right neighbor, else, 0.

Python Solution:

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        # Recurrence Relation: dp[i] = max(solve, skip) = max(points_i + points_after_brainpower_i, next_question)
        # If next_question is out of bound, set it to 0
        # solve: current question's pts + the pts we can get after brainpower_i questions 
        # skip: max pts from the next question

        # TC: O(n), n=len(questions), SC: O(n)
        dp = [0] * len(questions)
        ans = 0
        for i in range(len(questions)-1, -1, -1):
            # Find solve_pts
            nextPts = dp[i + questions[i][1] + 1] if i + questions[i][1] + 1 < len(questions) else 0
            solve_pts = questions[i][0] + nextPts
            # Find skip_pts
            skip_pts = dp[i+1] if i+1 < len(questions) else 0
            dp[i] = max(solve_pts, skip_pts)
            ans = max(ans, dp[i])
        return ans

Time Complexity: $O(n)$
Space Complexity: $O(n)$