Masseuse (question number uncertain)

The title

A reputable massage therapist will receive a steady stream of requests for appointments, each with an opt-in option. There must be a break between each appointment, so she cannot accept adjoining appointments. Given a sequence of appointment requests, find the best set of appointments for the masseuse (maximum total appointment time) and return the total number of minutes.

Note: There are some changes in this topic

Example 1:

Input: [1,2,3,1] Output: 4 Description: Select reservation 1 and reservation 3, total duration = 1 + 3 = 4.Copy the code

Example 2:

Input: [2,7,9,3,1] Output: 12 Description: Select appointment 1, appointment 3, and appointment 5, total duration = 2 + 9 + 1 = 12.Copy the code

Example 3:

Input: [2,1,4,5,3,1,1,3] Output: 12 Explanation: Select appointment 1, appointment 3, appointment 5 and appointment 8, total duration = 2 + 4 + 3 + 3 = 12.Copy the code

explain

Classical dynamic programming, one of the simpler ones, is a great way to recall dynamic programming.

It’s a little bit like buying and selling stocks and taking a day off, but it’s a little bit easier, you don’t have to subtract, you just add the values.

Because we need to rest for a day, the DP status can be:

DP [I] [not to make an appointment on the same day] = math.h Max (DP [I - 1] [] on the day of the reservation, DP [I - 1] [not to make an appointment on the same day]) DP [I] [] on the day of the reservation = DP [not to make an appointment on the same day] [I - 1] + appointment that dayCopy the code

Or it can be converted to a single array, where the initial value needs to be assigned one more time, and the loop starts at 2, so you can directly determine the maximum appointment time of the day.

DP[I] = math.max (DP[i-2] + appointment time, DP[i-1])Copy the code

You can do it either way. There’s not much difference.

Your own answers (even numbers)

var massage = function(nums) { var len = nums.length arrHas = new Array(len) arrNone = new Array(len) if (! len) return 0 arrHas[0] = nums[0] arrNone[0] = 0 for (let i = 1; i < len; i++) { arrHas[i] = arrNone[i - 1] + nums[i] arrNone[i] = Math.max(arrHas[i - 1], arrNone[i - 1]) } return Math.max(arrHas[len - 1], arrNone[len - 1]) };Copy the code

The arrHas array indicates the day of the appointment, and the arrNone array indicates the day of the rest. Finally, the maximum value of the last element of the two can be used.

Your own answer (dimension reduction)

var massage = function(nums) { var len = nums.length order = nums[0] rest = 0 if (! len) return 0 for (let i = 1; i < len; i++) { [order, rest] = [rest + nums[i], Math.max(order, rest)] } return Math.max(order, rest) };Copy the code

According to the above answer, in fact, it only needs to record two different states of rest and appointment on the previous day, so it can be extracted directly into two variables: Order represents appointment on the previous day, and REST represents rest on the previous day.

Use destruct assignments to update order and REST each time you loop, eliminating the need for intermediate steps.

Using the second DP formula in the explanation can also be used, but the calculation of the day’s formula requires a simple change, no problem.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ