LC-2140 Medium LeetCode

2140. Solving Questions With Brainpower

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 60% Topics: Array, Dynamic Programming

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# dp
class Solution(object):
    def mostPoints(self, questions):
        """
        :type questions: List[List[int]]
        :rtype: int
        """
        dp = [0]*(len(questions)+1)
        for i in reversed(xrange(len(dp)-1)):
            dp[i] = max(dp[i+1], questions[i][0] + (dp[i+1+questions[i][1]] if i+1+questions[i][1] < len(dp) else 0))
        return dp[0]

Solution from kamyu104/LeetCode-Solutions · MIT