Skip to main content

2140. Solving Questions With Brainpower

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

Python​

Top Down DP​

from functools import cache


class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        @cache
        def dfs(i):
            if i >= len(questions):
                return 0
            point, skip_step = questions[i][0], questions[i][1]
            take = dfs(i+skip_step+1) + point
            skip = dfs(i+1)

            return max(take, skip)
        
        return dfs(0)

Bottom Up DP​

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):
            take = questions[i][0]
            skip = questions[i][1]

            next_ques = min(n, i+skip+1)
            dp[i] = max(dp[i+1], take + dp[next_ques])

        return dp[0]