“This is the third day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Sponsored by Amazon company Leetcode Weekly Contest 276, outstanding people can also obtain the interview opportunity of Amazon company (admire), look at the list of the first is a player from Peking University, win glory for the country, as long as the first nationality is Chinese, we model, my level is ashamed. This paper introduces the third question in week 276. The difficulty is Medium. It takes one hour, and it is not too difficult, but I feel a little bit too short to finish it.

describe

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]]:
  • 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.

Example 1:

Input: questions = [[3, 2], [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.Copy the code

Example 2:

Input: questions = [[1, 1], [2], [3, 3], [4], [5, 5]] Output: 7 Explanation: The maximum points can be earned by solving questions 1 and 4. - Skip question 0 - Solve question 1: Earn 2 points, will be unable to solve the next 2 questions - Unable to solve questions 2 and 3 - Solve question 4: Earn 5 points Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.Copy the code

Note:

1 <= questions.length <= 105
questions[i].length == 2
1 <= pointsi, brainpoweri <= 105
Copy the code

parsing

Questions [I] = [pointsi, brainpoweri] questions[I] = [pointsi, brainpoweri] This array describes the questions on the exam, which must be dealt with sequentially from left to right, but each question can be resolved or skipped. If you choose to solve Questions [I] you will win pointsi points, but will not solve the following Brainpoweri problem. If you skip problem I, you can move on to the next problem.

  • For example, given the questions = [[3, 2], [4, 3], [4, 4], [2, 5]] :
  • If you solve problem 0, you will get 3 points, but you will not be able to solve problems 1 and 2
  • If you skip question 0 to solve question 1, you will get 4 points, but you will not be able to solve questions 2 and 3.

The highest score achieved by passing the exam is returned.

  • First of all, I use POS to find the index of the next problem that can be solved if the I problem is solved.
  • Then use the DFS function, which represents the maximum score that can be obtained by starting at I positions
  • The position of all questions is traversed and DFS (J, questions[j][0]) is calculated to get the maximum score in the end

My solution used recursion, but timed out because of DFS and two loops, resulting in O(n^3).

answer

class Solution(object):
    def mostPoints(self, questions):
        """
        :type questions: List[List[int]]
        :rtype: int
        """
        pos = []
        N = len(questions)
        for i,(coin, brainpower) in enumerate(questions):
            pos.append(min(i+brainpower+1, N))
        def dfs(i, coins):
            if i >= N - 1 or pos[i]>=N:
                return coins
            return max([dfs(j, coins + questions[j][0]) for j in range(pos[i], N)])

        return max([dfs(j, questions[j][0]) for j in range(N)])
        
        	      
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

Saw the solution to other bosses, I found my train of thought should be changed, should not be used to, but from the back, forward for every problem we all know that there are two kinds of schemes, one is jumped and execute the next topic, another kind is to solve the current problems and several to skip this topic, ask us to finally get the scores, the biggest dynamic planning topics, this is typical of We use the idea of dynamic programming to traverse questions from back to front and define dp[I] as the maximum score that can be collected by questions[I :]. The length is N+1. Because we are going to use dp[N] to store the value of indexes beyond the length of questions as 0, the formula of dynamic programming is

dp[i] = max(points + dp[min(jump + i + 1, len(questions))], dp[i + 1])
   
Copy the code

After traversing from back to front, return dp[0]. Return dp[0]. Time is O(n), space is O(n).

answer

class Solution(object):
    def mostPoints(self, questions):
        """
        :type questions: List[List[int]]
        :rtype: int
        """
        dp = [0] * (len(questions) + 1) 
        for i in range(len(questions) - 1, -1, -1):
            points, jump = questions[i][0], questions[i][1]
            dp[i] = max(points + dp[min(jump + i + 1, len(questions))], dp[i + 1])
        return dp[0];
Copy the code

The results

Runtime: 2241 ms
Memory Usage: 65.5 MB
Copy the code

Original link: leetcode.com/contest/wee…