I punch simple algorithm questions | leetcode. [17.16] interview questions massage therapist – JAVA

This is the fifth day of my participation in Gwen Challenge

The original problem

Interview question 17.16. Masseuse

A reputable masseuse receives a steady stream of requests for appointments, each with the option of taking or not taking them. There is a break between each appointment, so she cannot accept adjacent appointments. Given a sequence of appointment requests, find the optimal set of appointments for the massage therapist (with the longest total appointment time) and return the total number of minutes.

Example 1:

Input:1.2.3.1] output:4Explanation: Choice1To make an appointment and3On, total duration =1 + 3 = 4.Copy the code

Example 2:

Input:2.7.9.3.1] output:12Explanation: Choice1To make an appointment,3To make an appointment and5On, total duration =2 + 9 + 1 = 12.Copy the code

Example 3:

Input:2.1.4.5.3.1.1.3] output:12Explanation: Choice1To make an appointment,3To make an appointment,5To make an appointment and8On, total duration =2 + 4 + 3 + 3 = 12.Copy the code

jolt

Understand all understand, this problem is dynamic planning, the key is that he is simple problem 😘, so or in accordance with the basic routine.

First of all, I looked at the topic carefully. It looked like the kind of medium difficulty to plunder, but he was medium, so I did not study him.

• The boundary conditions

  The basic nums[I] array cannot be empty. It does not even have a default value, but I will take it as zero. Technician comrade after each work to rest, not continuous work, so when numS [I] length is less than or equal to 2, the basic can be simple to determine. So there are:

  
  $$\left\{ \begin{aligned} 0 & &\ n < 1 \\ nums[0] & &\ n < 2 \\ MAX(nums[0],nums[1]) & &\ n < 3 \\ \end{aligned} \right.$$

• subproblems

  If there are a total of N guests, the general dynamic planning topic is considered from the top down. For the last guest, the technician comrade has two options:

  1. For the firstnThe total time spent working with one guest isnums[n-1]Add to that the total amount of time spent working
  2. Don’t give the firstnThe time spent working for a guest is the firstn-1Total time spent working before one guest

  The above two cases can be recurred, so we can set the subquestion as the total time dp[n-1] spent doing work for the NTH guest

• equation

  According to the subproblem summarized in the previous paragraph, since technicians need to take a break after each work, continuous customers should not be used. So the above subproblem can be subdivided again:

  1. For the firstnAfter a guest works, the technician comrade can only fromn - 2Go forward in the customer to choose, at this time the problem can continue to set dolls
  2. Don’t give the firstnA guest work, the technician comrade can only fromn - 1Forward customers to choose, this time in front of the situation can set Eva

  Try listing the following state transition equation (array subscripts start at 0) :

  
  $$dp(n)=\left\{ \begin{aligned} 0 & &\ n < 1 \\ nums[0] & &\ n < 2 \\ MAX(nums[0],nums[1]) & &\ n < 3 \\ Max(nums[n – 1] + dp[n – 3], dp[n – 2]) & &\ n >= 3 \\ \end{aligned} \right.$$

• Write code that combines conditions

      public int massage(int[] nums) {
          int length = nums.length;
          // Base case judgment
          if (length < 1) {
              return 0;
          } else if (length < 2) {
              return nums[0];
          } else if (length < 3) {
              return Math.max(nums[0], nums[1]);
          }
  		
          // subproblem, initialize dp
          int[] dp = new int[length ];
          dp[0] = nums[0];
          dp[1] = Math.max(nums[0], nums[1]);
          // Change the code according to the dynamic transfer equation
          for (int i = 3; i < length + 1; i++) {
              dp[i - 1] = Math.max(nums[i - 1] + dp[i - 3], dp[i - 2]);
          }
          return dp[length - 1];
      }
  Copy the code

  It then runs and finds that ** execution time beats 100.00% and memory beats 92.83%

closed

• Finding the right subproblems for dynamic specification problems is really helpful
• Memory consumption can be achieved by using severalintType parameter to always replacedpAn array of