< Back





2140. Solving Questions With Brainpower

Fun dynamic programming question, similar to 198. House Robber. The difference
is that during house robber we were making two choices, the next house (i + 1), or the house after
the next one (i + 2). In this problem, the number of choices we skip can be anywhere from 1 to 10^5.

We solve it with a similar approach, and I'll show both the recursive and iterative solutions. The
recursive solution is top-down. Starting from index 0, I'll recursively solve the succeeding problems
and reuse computations by storing answers in a table. During each decision, we make sure we're not
out of range and that this question already hasn't been solved. Then we proceed to take the max of
our two choices:

  1. Skip the current question and solve the next one.
  2. Solve the current question and solve the question that is i + questions[i][1] + 1 away, where i
  is the current index.

Eventually we'll reach the end of the questions list and then the recursion will collapse as it
returns base cases.

For the iterative solution, we also create a table to memoize our answer. This time, we'll be doing a
bottom-up approach, starting from the second to last element in the questions list. We make the same
two choices, to solve the current question and the question that is i + questions[i][1] + 1 away, or
to skip the current question and solve the next one. We store the maximum of these two choices in our
table and continue until we reach the first element in the questions list.

The recursive solution is as follows:


  class Solution:
      def mostPoints(self, questions: List[List[int]]) -> int:
          n = len(questions)
          memo = [0] * n

          def dp(i: int):
              if i > n - 1:
                  return 0

              if memo[i]:
                  return memo[i]

              memo[i] = max(dp(i + 1), dp(i + questions[i][1] + 1) + questions[i][0])

              return memo[i]

          return dp(0)


The iterative solution is as follows:


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

          for i in range(n - 2, -1, -1):
              memo[i] = questions[i][0]

              if i + questions[i][1] + 1 < n:
                  memo[i] += memo[i + questions[i][1] + 1]

              memo[i] = max(memo[i], memo[i + 1])

          return memo[0]


_ Time Complexity:

  O(n) - Where n is the length of questions, we solve each question once.

_ Space Complexity:

  O(n) - We maintain a table of length n to memoize our answers.