2140. Solving Questions With Brainpower | 1709

 1class Solution:
 2    def mostPoints(self, questions: List[List[int]]) -> int:
 3        # intuition: backtracking
 4        # backtrack alone TLEs - is it O(2**n) or O(n**2)?
 5        # lru_cache(None) MLEs
 6        # integrate DP
 7        # state = ?
 8
 9        n = len(questions)
10
11        def bt(pts: int, idx: int) -> int:
12            if idx > n - 1:
13                return pts
14
15            return max(
16                bt(pts + questions[idx][0], idx + questions[idx][1] + 1),
17                bt(pts, idx + 1),
18            )
19
20        return bt(0, 0)

 1class Solution:
 2    def mostPoints(self, questions: List[List[int]]) -> int:
 3        # intuition: backtracking + memo
 4        # bt(pts so far, idx)
 5        # backtrack alone TLEs - is it O(2**n) or O(n**2)?
 6        # lru_cache(None) MLEs
 7        # integrate DP
 8        # state = "maximum points earnable starting from idx"
 9
10        n = len(questions)
11
12        @lru_cache(None)
13        def bt(idx: int) -> int:
14            if idx > n - 1:
15                return 0
16
17            points, brainpower = questions[idx]
18
19            return max(points + bt(idx + brainpower + 1), bt(idx + 1))
20
21        return bt(0)