~/leetcode$cat2140. Solving-Questions-With-Brainpower

This question sounds like a classic dynamic programming problem.

When we iterate through the questions in order, we have two options:

• we can either solve the problem or skip it
• if we solve the problem, we cannot answer the next brainpower[i] questions
• if we don’t solve the problem, we can consider the next question

Therefore, the dp recurrence would be:

• let dp[i] is the max score before considering up to i questions

I’ve been thinking on this for 30 minutes and I still can’t figure it out so I took a look at the top 2 hints:

• they have chosen to store for each question, the maximum points we can earn if we started the exam on that question
• this suggests iterating through the list backwards which is kind of big brain

The dp recurrence for dp[i] is thus:

• if we choose to solve the current question, dp[i] = points + dp[next_answerable_q]
• if we choose to skip this question, dp[i] = dp[i + 1]
• we can take the maximum of these for our overall dp[i]: dp[i] = max(points + dp[next_answerable_q], dp[i + 1]

Then at the end, we can return dp[0] for our answer. We just have one edge case to consider:

• when the next position is outside of the range, if we solve the question, dp[i] = points

class Solution(object):
    def mostPoints(self, questions):
        """
        :type questions: List[List[int]]
        :rtype: int
        """
        n = len(questions)
        dp = [0] * n
        dp[n - 1] = questions[n - 1][0]

        for i in range(n - 2, -1, -1):
            point, brainpower = questions[i]
            next_pos = i + brainpower + 1

            if next_pos > n - 1:
                dp[i] = max(point, dp[i + 1])
            else:
                dp[i] = max(point + dp[next_pos], dp[i + 1])

        return dp[0]

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 42m 16s - this took me way too long to figure out, Eric did it the way I was thinking initially, I still don’t know what was different between his solution and mine

Extras:

I solved it using my initial method (so without the hint (BIG COPIUM)), so I just wanted to share how goofy I am below:

Therefore, the dp recurrence would be:

• let dp[i] is the max score before considering up to i questions

This would just be the reverse of the solution above:

• when we consider questions[i]:
  • if we solve the question, dp[next_pos] = max(points + dp[i], dp[next_pos]
  • if we skip the question, dp[i + 1] = max(dp[i], dp[i + 1])

Therefore, we do both updates to account for both cases.

class Solution(object):
    def mostPoints(self, questions):
        """
        :type questions: List[List[int]]
        :rtype: int
        """
        n = len(questions)
        dp = [0] * n
        largest = 0

        for i in range(n):
            point, brainpower = questions[i]
            next_pos = i + brainpower + 1
            if next_pos < n:
                dp[next_pos] = max(dp[i] + point, dp[next_pos])
            else:
                largest = max(largest, dp[i] + point)
            if i < n - 1:
                dp[i + 1] = max(dp[i], dp[i + 1]) 

        return largest

The problem that I had was that I was not updating dp[i + 1] if I hit the else case (I put the dp[i + 1] update inside the if next_pos < n block). Big goof moment.