Skip to content

2140. Solving Questions With Brainpower

On LeetCode ->

Problem

Choose which questions to solve in order. Solving question \(i\) earns its points but prevents you from solving the next brainpower questions. Find the maximum total.

questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
output = 5  (solve questions 0 and 3)

Key trick

Work backward: at each question, compare skipping it with solving it and continuing at index i + brainpower + 1.

Trap

The next question available after solving \(i\) is i + brainpower + 1, not i + brainpower.

Why is it interesting?

It resembles house robber, but each choice jumps a different distance.

Python solution

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

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

            # Skip i, or solve it and continue at the next eligible question.
            solve = points + (dp[nxt] if nxt < n else 0)
            dp[i] = max(dp[i + 1], solve)

        return dp[0]

Time: \(O(n)\). Space: \(O(n)\).

Comment on my solution

Your forward propagation idea can work, but the solve transition has an off-by-one error: i + b must be i + b + 1. For example, your code allows both questions in [[3, 1], [4, 1]] and returns 7 instead of 4. Each set also stores scores you ultimately discard; one best score per index is enough.

# Ideas:
# - take or skip problem (maybe like house robber)

class Solution:
    def mostPoints(self, questions: list[list[int]]) -> int:
        n = len(questions)
        previous = [set() for _ in range(n)]
        best = 0
        for i, (p, b) in enumerate(questions):
            max_prevs = 0
            if previous[i]:
                max_prevs = max(previous[i])

            # skip questions[i]
            if i + 1 < n:
                previous[i + 1].add(max_prevs)

            # solve questions[i]
            if i + b < n:
                previous[i + b].add(max_prevs + p)

            best = max(best, max_prevs + p)

        return best

# WORKS
# implemented after reading AI comments
# I made an off-by-one error: i + b -> i + b + 1
class Solution:
    def mostPoints(self, questions: list[list[int]]) -> int:
        n = len(questions)
        previous = [set() for _ in range(n)]
        best = 0
        for i, (p, b) in enumerate(questions):
            max_prevs = 0
            if previous[i]:
                max_prevs = max(previous[i])

            # skip questions[i]
            if i + 1 < n:
                previous[i + 1].add(max_prevs)

            # solve questions[i]
            if i + b + 1 < n:
                previous[i + b + 1].add(max_prevs + p)

            best = max(best, max_prevs + p)

        return best

Solution().mostPoints([[3,2],[4,3],[4,4],[2,5]])
Solution().mostPoints([[1,1],[2,2],[3,3],[4,4],[5,5]])