Ninja’s Training

PROBLEM STATEMENT

Ninja is planing this ‘N’ days-long training schedule. Each day, he can perform any one of these three activities. (Running, Fighting Practice or Learning New Moves). Each activity has some merit points on each day. As Ninja has to improve all his skills, he can’t do the same activity in two consecutive days. Can you help Ninja find out the maximum merit points Ninja can earn?

You are given a 2D array of size N*3 ‘POINTS’ with the points corresponding to each day and activity. Your task is to calculate the maximum number of merit points that Ninja can earn.

For Example

If the given ‘POINTS’ array is [[1,2,5], [3 ,1 ,1] ,[3,3,3] ],the answer will be 11 as 5 + 3 + 3.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer,' N’, denoting the number of days.

The next ‘N’ lines of each test case have 3 integers corresponding to POINTS[i].

Output Format:

For each test case, return an integer corresponding to the maximum coins  Ninja can collect.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 100000.
1 <= values of POINTS arrays <= 100 .

Time limit: 1 sec

Approach 1

As given in the question, if we do the jth activity on day i, then Ninja cant repeat the activity on day i+1. So, we will define a recursive function REC(N,i, POINTS) that will return the maximum merit points till the Nth day, and he did the ith activity on the Nth day.

We can recursively find the value of REC(N,i, POINTS) as POINTS[N-1][i] + maximum among REC(N-1,i-1, POINTS) and REC(N-1,i-1, POINTS) for i different from the current choice of activity.

The final answer will be the maximum of REC(N,i, POINTS) among all three values of i.

Algorithm:

Defining 'REC'(N, i,’ POINTS’) function :
- If N is 0:
  - No days left.
  - Return 0.
- Set ‘ANS’ as POINTS[N-1][i-1].
- If i == 1:
  - Set MX as maximum as REC(N-1,2,POINTS) and REC(N-1,3,POINTS).
- If i == 2:
  - Set MX as maximum as REC(N-1,1,POINTS) and REC(N-1,3,POINTS).
- If i == 3:
  - Set MX as maximum as REC(N-1,1,POINTS) and REC(N-1,2,POINTS).
- Return ‘ANS’ + ‘MX’.
Set ‘ANS’ as 0.
Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,1, POINTS).
Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,2, POINTS).
Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,3, POINTS).
Return ‘ANS’.

Try Problem

Approach 2

In this approach, we will use the same recursive functions, we used in approach 1 but we will use memoization to reduce the complexity as the answer for each state will be calculated only once.

We will define a 2D array ‘DP’ to store the answers.

Algorithm:

Defining 'REC'(N, i,’ POINTS’, ‘DP’) function :
- If N is 0:
  - No days left.
  - Return 0.
- If DP[N][i] is not equal to -1:
  - Pre Computed value found.
  - Return DP[N][i].
- Set ‘ANS’ as POINTS[N-1][i-1].
- If i == 1:
  - Set MX as maximum as REC(N-1,2,POINTS,DP) and REC(N-1,3,POINTS,DP).
- If i == 2:
  - Set MX as maximum as REC(N-1,1,POINTS,DP) and REC(N-1,3,POINTS,DP).
- If i == 3:
  - Set MX as maximum as REC(N-1,1,POINTS,DP) and REC(N-1,2,POINTS,DP).
- Set DP[N][i] as ‘ANS’ + ‘MX’.
- Return ‘ANS’ + ‘MX’.

Declare a 2-D array ‘DP’ to memoize this DP solution.
Set each value of ‘DP’ as -1.
Set ‘ANS’ as 0.
Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,1, POINTS).
Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,2, POINTS).
Set ‘ANS’ as the maximum of ‘ANS’ and REC(N,3, POINTS).
Return ‘ANS’.

Try Problem

Approach 3

In this approach, we will make a 2D ‘DP’ array of size N*4 .’DP’[i][j] will return the maximum merit points till the ith day and he did the jth activity on the Nth day.

Base cases of the DP solution will be:

The values of DP[0][i] will be 0 for all values of i as there is no days left.

To compute DP[i][0], as we can’t do the first activity at day i-1, so we will pick the maximum among second and third activity for the day (i-1) plus the merit points for the first activity at ith day (POINTS[i-1][0]).

So,value of DP[i][0] = POINTS[i-1][0] + max(DP[i-1][1],DP[i-1][2]).

Similarly,

Value of DP[i][1] will be POINTS[i-1][1] + max(DP[i-1][0],DP[i-1][2]).

and Value of DP[i][2] will be POINTS[i-1][2] + max(DP[i-1][0],DP[i-1][1]).

The final answer will be maximum among values DP[‘N’][i] for all 3 values of i.

Algorithm:

Declare a 2-Dimensional array ‘DP’ of size ‘N’ * ’4’.
For i in range 0 to N-1:
- If i is equal to 0:
  - Set DP[i][j] as POINTS[i][j].
  - Continue.
- Set DP[i][1] as POINTS[i-1][0] + maximum of DP[i-1][2] and DP[i-1][3].
- Set DP[i][2] as POINTS[i-1][1] + maximum of DP[i-1][1] and DP[i-1][3].
- Set DP[i][3] as POINTS[i-1][2] + maximum of DP[i-1][1] and DP[i-1][2].