JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

DPL7 Ninja's Training or Vacation Atcoder 2D DP 🔥

A Ninja has an ‘N’ Day training schedule. He has to perform one of these three activities (Running, Fighting Practice, or Learning New Moves) each day. There are merit points associated with performing an activity each day. The same activity can’t be performed on two consecutive days. We need to find the maximum merit points the ninja can attain in N Days.

We are given a 2D Array POINTS of size ‘N*3’ which tells us the merit point of specific activity on that particular day. Our task is to calculate the maximum number of merit points that the ninja can earn.

Greedy Approch
Accroding to the Greedy we find the Best Solution on the every Point that is the Defination of the Greedy Algorithm

So if we used the Greedy then our ans may be not correct let's understand

On Day 0, we will consider the activity with maximum points i.e 50

On Day 1, the maximum point activity is 100 but we can’t perform the same activity in two consecutive days. Therefore we will take the next maximum point activity of 11 points.

TAccording to the Greedy Solution : 50+11 = 61(Ans)

Hence Proved Not Every time Greedy is Correct for the Expected Ans

As this is a small example we can clearly see that we have a better approach, to consider activity with 10 points on day0 and 100 points on day1. It gives us the total merit points as 110 which is better than the greedy solution.

Recursice Approch

Steps to form the recursive solution
Step 1: Express the problem in terms of indexes:

We are given an N*3 Matrix which can be easily thought of in terms of indexes(Days), It is the number of days. Clearly, we have n days (from 0 to n-1), so one changing parameter which can be expressed in terms of indexes is ‘day’ fun(day).

Every day we have the option of three activities(say 0,1,2) to be performed so we required the one more parameter that is tarck the record of last Day becouse the Question say we can nto perform the same task on consecutive days fun(day,last)

Every iht_day we have a three task(0,1,2) and we try to iterate all the task of the day that is != last. Therefore our function will take two parameters – day and last.

Step 2: Try all the choices to reach the goal. & Try out all possible choices at a given index.
We are writing a top-down recursive function. We start from day n-1 to day 0. Therefore whenever we call the recursive function for the next day we call it for fun(day-1, second parameter). Now let’s discuss the second parameter. The choices we have for a current day depend on the ‘last’ variable. If we are at our base case (day=0), we will have the following choices.

Other than the base case, whenever we perform an activity ‘i’ its merit points will be given by points[day][i] and to get merit points of the remaining days we will let recursion do its job by passing fun(day-1, i). We are passing the second parameter as i because the current day’s activity will become the Next day’s last.

Step 3: Take the maximum of all the choices

As the problem statement wants us to find the maximum merit points, we will take the maximum of all choices.

Recursion Base Conditions
The base conditions for the recursive Solution

If DAY=0, then we try (0,1,2) all the task for the finding the out max Ans, that is task is != to the last, Max = max(Max,points[0][i]) and return Max

Recursion Tree

Time & Space Complexity

Time Complexity: O(N*4*3)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Steps to convert Recursive code to memoization solution:

Create a dp array of size [n][4]. There are total ‘n’ days and for every day, there can be 4 choices (0,1,2 and 3). Therefore we take the dp array as dp[n][4]. Inilisized with the -1

Whenever we want to find the answer of particular parameters (say fun(day,last)), we first check whether the answer is already calculated using the dp array(i.e dp[day][last]!= -1 ). If yes, simply return the value from the dp array. dp[day][last]

If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[day][last] to the solution we get.

Time & Space Complexity

Time Complexity:O(N*4*3)
Reason: There are N*4 states and for every state, we are running a for loop iterating three times.
Space Complexity: O(N) + O(N*4)
Reason: We are using a recursion stack space(O(N)) and a 2D array (again O(N*4)). Therefore total space complexity will be O(N) + O(N) ≈ O(N)

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

Steps to convert Recursive Solution to Tabulation one.

Declare a dp[] array of size [n][4]

• First initialize the base condition values. We know that base condition arises when day = 0. Therefore, we can say that the following will be the base conditions
  • dp[0][0] = max(points[0][1], points[0][2])
  • dp[0][1] = max(points[0][0], points[0][2])
  • dp[0][2] = max(points[0][0], points[0][1])
  • dp[0][3] = max(points[0][0], points[0][1] and points[0][2])

Set an iterative loop which traverses dp array (from index 1 to n) and for every index set its value according to the recursive logic

Time & Space Complexity

Time Complexity: O(N*4*3)
Reason:There are three nested loops
Space Complexity: O(N*4)
Reason: We are using an external array of size ‘N*4’’.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: ( i,i-1,i-2,i-3) for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

Initially we filled the dp[0]th row entire & we clearly see int the tabulation Methode we used the dp[day-1] + something that is our ans

dp[day][last] = max(dp[day][last],points[day][task] + dp[day-1][task]) Here the task can be anything from 0 to 3 and day-1 is the previous stage of recursion. So in order to compute any dp array value, we only require the last row to calculate it.

So rather than storing the entire 2D Array of size N*4, we can just store values of size 4(say prev).

We can then take a dummy array, again of size 4 (say temp) and calculate the next row’s value using the array we stored in step 1.

After that whenever we move to the next day, the temp array becomes our prev for the next step.

At last prev[3] will give us the answer.

Time & Space Complexity

Time Complexity:O(N*4*3)
Reason: There are three nested loops
Space Complexity: O(4)
Reason: We are using an external array of size ‘4’ to store only one row.