Minimum Work

In this approach, We can use recursion to generate all possible valid tasks assignment. Let us define a recursive function that depends on the parameters (current_task and last_task) where current_task denotes the task we are currently doing and the last_task denotes the last task that we did. 

Now for any task, we can either assign that task to ourselves or skip that task. We can skip that task only if the tasks skipped between the last task and the current task is not greater than 2. Let us modify the function parameters a little with new parameters as (the index of the current task (‘IDX’) and the count of the tasks skipped between the last tasks and current task(‘LAST’)). Now we can define the recurrence relation as:

If ‘LAST’ < 2:

F(IDX, LAST) = minimum of ( F(IDX+1, LAST + 1), ‘TIMES[ IDX ]’ + F(IDX+1, 0 ) ).

Else:

F(IDX, LAST) = ‘TIMES[ IDX ]’ + F(IDX+1, 0 ).

The steps are as follows:-

// Recursive function to get minimum time

function getMinWorkUtil( [ int ] times, int idx, int last):

1. If the value of last is 3 then return 1e7.
2. If the value of 'IDX' is greater or equal to 'N' then return  0.
3. Recursively call the 'getMinWorkUtil' function by first taking the current work and then not taking the current work and then return the minimum of the values returned by them.

Function getMinWork( [ int ] times):

1. Call the 'getMinWorkUtil' function and store the value returned in the 'ANS' variable.
2. Return the value of the 'ANS' variable.

In this approach, we are going to optimize the previous approach. The recursive function is defined by two parameters (IDX, LAST). If we observe carefully we will find that we are calculating the value for some (IDX, LAST) more than once. We can use a matrix to store the values returned by every function call.

The steps are as follows:-

// Recursive function to get minimum time

function getMinWorkUtil( [ int ] times, int idx, int last):

1. If the value of last is 3 then return 1e7.
2. If the value of 'IDX' is greater or equal to 'N' then return  0.
3. If the value of 'DP[ idx ][ last ]' is not equal to -1 the return the value of 'DP[ idx ][ last ]'.
4. Recursively call the 'getMinWorkUtil' function by first taking the current work and then not taking the current work. Store the minimum of the values returned by them in 'DP[idx][last]' and return it.

Function getMinWork( [ int ] times):

1. Initialize a 2d matrix 'DP' of size 'N' x 3 with value -1.
2. Call the 'getMinWorkUtil' function and store the value returned in the 'ANS' variable.
3. Return the value of the 'ANS' variable.

In this approach, the idea is that for any task, we will find the minimum time required to complete such that all the tasks before that were completed optimally. If all the tasks before that were completed optimally then the minimum time needed for the current task is the time to complete the current task +  (let the index of the current task is ‘i’) minimum time of (‘i’ - 1)th task, (‘i’ - 2)th task and (‘i’ - 3)th task.

We can find the minimum for any task and store it in an array and then use that array to solve the minimum time for the next tasks. 

The steps are as follows:-

Function getMinWork( [ int ] times):

1. Initialize an array 'DP' of size 'N' + 1 with value 1e9.
2. Modify 'DP[ 0 ]' = 0.
3. Run a loop from 'i' = 1 to 'N':
   • Run a loop from 'j' = ('i' - 1) to ('i' - 3) (also check if 'j' >= 0):
     • Update the value of 'DP[ i ]' to the minimum of  'DP[ i ]' and ('times[ i - 1 ] + 'DP[ j ]').
4. Initialize a variable 'ANS' with value 1e9.
5. Store the minimum of 'DP[ n ], DP[ n - 1 ] and 'DP[ n - 2 ]' in the variable 'ANS'.
6. Return the value of the 'ANS' variable.