Problem of The Day: Solving Questions With Brainpower

Problem Statement

Memoization Approach [MLE]

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        N = len(questions)
        memo = {}
        def helper(i, points):
            if i >= N:
                return points
            if (i, points) in memo:
                return memo[(i,points)]
            point, brainpower = questions[i]
            solve = helper(i + brainpower + 1, points + point)
            skip = helper(i + 1, points)
            memo[(i, points)] = max(solve, skip)
            return memo[(i, points)]

        return helper(0, 0)

Improved Memoization Algorithm - Top down

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        N = len(questions)
        memo = {}

        def helper(i):
            if i >= N:
                return 0  # Base case: No more questions to answer
            if i in memo:
                return memo[i]

            point, brainpower = questions[i]

            # Option 1: Solve the question
            solve = point + helper(i + brainpower + 1)

            # Option 2: Skip the question
            skip = helper(i + 1)

            memo[i] = max(solve, skip)
            return memo[i]

        return helper(0)

Dynamic programming Approach - Bottom up

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        N = len(questions)
        dp = [0] * N
        questions.reverse()
        for i, [point, brainpower] in enumerate(questions):
            prev_point = 0
            if i - brainpower - 1 >= 0:
                prev_point += dp[i - brainpower - 1]
            dp[i] = max(dp[i - 1], prev_point + point)

        return dp[-1]