Skip to content

Problem

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.

  • For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5|3, 2], [4, 3], [4, 4], [2, 5]]:
    • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
    • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

Constraints:

  • 1 <= questions.length <= 105
  • questions[i].length == 2
  • 1 <= pointsi, brainpoweri <= 105

Example 1:

**Input:** questions = [[3,2],[4,3],[4,4],[2,5|3,2],[4,3],[4,4],[2,5]]
**Output:** 5
**Explanation:** The maximum points can be earned by solving questions 0 and 3.

- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Solve

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

This is the one I come up with:

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        self.n = questions.__len__()
        self.trace = [[0,0] for i in range(self.n)]
        i = 0
        for v,bp in questions[::-1]:
            if i > 0:
                self.trace[i][0]=max(self.trace[i-1][0], self.trace[i-1][1])
            if i-bp-1<0:
                self.trace[i][1] = v
            else:
                self.trace[i][1] = v + max(self.trace[i-bp-1][0], self.trace[i-bp-1][1])
            i+= 1

        return max(self.trace[self.n-1][0], self.trace[self.n-1][1])

First look

Problem analised

Giving the problem with the skipping, it get a bit tricky:

  1. Let say you go from the first to last question,
    1. If there is only one question questions[0], then chose to do the first question questions[0] will give the most point. We have maxPoint( questions[0] ) = q[0].value
    2. But if there is 2 question, there will be 2 case:
      1. We want to do the second question, which lead to 2 child case:
        1. We want to do only the second question:
          1. This mean questions[1].value >= question[0].value
          2. questions[0] .brainPower >= 1: which mean if we try to do it, we need to skip at least 1 question, meanning skip the second question questions[1]
          3. maxPoint( questions[0..1] ) = q[1].value
        2. We can do both questtion
          1. questions[0] .brainPower == 0: which mean if we try to do it, we can still do the second question questions[1]
          2. maxPoint( questions[0..1] ) = q[1].value + q[0].value
      2. We don’t want to do the second question
        1. This mean questions[1] . value < question[0] .value
        2. questions[0] .brainPower >= 1: which mean if we try to do it, we need to skip at least 1 question, meanning skip the second question questions[1]
        3. maxPoint( questions[0..1] ) = q[0].value
    3. Let keep it going: add the third question, the best point of current could be:
      1. We want to do the third question
        1. We want to do only the third question
          1. This mean questions[2] . value >= the maxPoint(question[0..1])
          2. Also, questions[i] .brainPower >= 1 + i (i=[0..1]) : which mean if we try to do it, we need to skip the third question questions[2]
          3. We could see a recusive approad here
        2. We could do the third question, but we need to find
          1. questions[i] .brainPower < 1 + i (i=[0..1]): which mean if we do it, we can still do the third question questions[2]
          2. Here, we can see a bad partent:
            1. If we can find a matching questions[i] .brainPower < 1+ i: maxPoint(question[0..i]) still isn’t mean we have used questions[i] in it
            2. Which lead to a seperated:
              1. maxPoint(question[0..i]) that use questions[i] and have the corresponding questions[i].brainPower
              2. maxPoint(question[0..i]) that not questions[i] and we need to trace back which is the last question[j] (j != i) being done, and what is it’s corresponding brainPower
            3. This could mean we have to handle traceback/max table for each of there case
      2. We skip the third question: Well, which mean we can keep the maxPoint(question[0..1]) of two last question
  2. This could mean we have a O(n^2) if we not careful to handle the trace back and find the best maxPoint(question[0..i])

First implementation

Still, here could be the answer

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        self.n = questions.__len__()
        # Define trace array for trace back -1 mean we have no traceback; first value is the last question we do when we not do the question [i], second value is when we do the question [i] 
        self.trace = [[-1,i] for i in range(self.n)]
        # Define max array to give us a maxPoint table for cache the result instead of calling mostPoint over and over; Simmilar to trace, the first value is when we not do the question [i], second one is when we do the question[i] 
        self.max = [[0,0] for i in range(self.n)]
        i = 0
        for v,bp in questions:
            # Handle the first one
            if i==0:
                self.max[i][0]= 0
                self.max[i][1] = questions[0][0]
                self.trace[i][0] = -1
                self.trace[i][1] = 0
                continue

            # find max case
            innerMax = 0
            innerTrace = -1
            for innerIndex in range(i):
                if self.trace[innerIndex][0] != -1:
                    if innerMax < self.max[innerIndex][0]:
                        innerMax = self.max[innerIndex][0]
                        innerTrace = self.trace[innerIndex][0
                    if innerMax < self.max[innerIndex][0]:
                        innerMax = self.max[innerIndex][0]
                        innerTrace = self.trace[innerIndex][0]
                    # TODO............
            i+= 1

        return max(self.trace[self.n-1][0], self.trace[self.n-1][1])

The code it self become too much of a head ache; and also, the double for loop make me feel like there should be a better solution.

This is when i revaluate the aproad for better solution and also, fix the mess code above.

Revaluate

  1. We could go back-ward, doing the last question back to the first question.
    1. This make the brainPower from from skip “ahead” infomation problem (Which later information being rely on a lot of trace back info and need all history data for processing) : MaxPoint(question[0..i]) = max(question[i].value + maxPoint(question[0..i-1]) that isn't *require* question[i] to be skip, maxPoint(question[0..i-1]))
    2. into a skip “behind” problem (Which we can predicted exact infomation needed): when doing question[i], the maxPoint value after skipping question[i].brainPower will alway be question[i].value + maxPoint([i+question[i].brainPower .. n]) without any condition: maxPoint(question[i..n]) = max(question[i].value + maxPoint([i+question[i].brainPower .. n]), maxPoint(question[i+1..n]))
  2. Now that more like it; we not need to go and code to finding something weird like that isn't *require* question[i] to be skip

Recusive approad

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        if questions.__len__() == 0:
            return 0
        n = questions.__len__()
        v = questions[0][0]
        bp = questions[0][1]
        return max(v + self.mostPoints(questions[bp+1:n]), self.mostPoints( questions[1:n]))

quite slow tho; also, this is when i learn about @cache in python; it can’t be use for List type, so just global the question infomation and instead using index value as parameter. Here is a updated code

class Solution:
    @cache
    def maxPoints(self, x):
        if x>=self.n:
            return 0
        v = self.questions[x][0]
        bp = self.questions[x][1]
        return max(v + self.maxPoints(x+bp+1), self.maxPoints(x+1))


    def mostPoints(self, questions: List[List[int]]) -> int:
        self.n = questions.__len__()
        self.questions = questions
        return maxPoints(0)

Dynamic approad

Yeah, just do it at this point; These should be better to understand than my first submit

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = questions.__len__()
        maxTable = [0]*n
        maxTable[n-1] = questions[n-1][0]
        i = n-2
        for v, bp in questions[::-1]:
            if i+bp+1 < n:
                v += maxTable[i+bp+1] 
            maxTable[i] = max(v, maxTable[i+1])
            i -= 1
        return maxTable[0]
  1. The first submit code [i] value will be separate if I do it or not
  2. I using hard code to separate the len = 1 (which turn into an if statement inside the for loop in the first submit code)
  3. Invert the for loop index value from n down to 1; instead couting up 1 to n like in the first submit code.
Last update : October 13, 2023
Created : August 16, 2023