Solving Questions With Brainpower — LeetCode 2140 Python Solution

The problem

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri]. The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question.

Example

Input

questions = [[3,2],[4,3],[4,4],[2,5]]

Output

5

Explanation

The maximum points can be earned by solving questions 0 and 3.

Python solution

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(questions):
                return 0
            p, b = questions[i]
            return max(p + dfs(i + b + 1), dfs(i + 1))

        return dfs(0)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2140. Solving Questions With Brainpower is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems