Obsidian Notes

Ninja's Training

3 min read

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.

Detailed explanation ( Input/output format, Notes, Images )

Constraints:

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

Time limit: 1 sec

Sample Input 1:

2
3
1 2 5 
3 1 1
3 3 3
3
10 40 70
20 50 80
30 60 90

Sample Output 1:

11
210

Explanation of sample input 1:

For the first test case,
One of the answers can be:
On the first day, Ninja will learn new moves and earn 5 merit points. 
On the second day, Ninja will do running and earn 3 merit points. 
On the third day, Ninja will do fighting and earn 3 merit points. 
The total merit point is 11 which is the maximum. 
Hence, the answer is 11.

For the second test case:
One of the answers can be:
On the first day, Ninja will learn new moves and earn 70 merit points. 
On the second day, Ninja will do fighting and earn 50 merit points. 
On the third day, Ninja will learn new moves and earn 90 merit points. 
The total merit point is 210 which is the maximum. 
Hence, the answer is 210.

Sample Input 2:

2
3
18 11 19
4 13 7
1 8 13
2
10 50 1
5 100 11

Sample Output 2:

45
110

Approach - Tabulation 1D DP

  • We calculate DP with this logic
    • dp[0]: max points up to yesterday if you did Running yesterday
    • dp[1]: max points up to yesterday if you did Fighting yesterday
    • dp[2]: max points up to yesterday if you did Learning yesterday
    • dp[3]: max points up to yesterday if there was no restriction (used for day 0 base case)
  • O(n*4*3), O(4)
public class Solution {
    public static int ninjaTraining(int n, int points[][]) {
 
        // Write your code here..
        int[] dp = new int[4];
        
        //base case day 1
        dp[0] = Math.max(points[0][1], points[0][2]); //if last day had 0
        dp[1] = Math.max(points[0][0], points[0][2]); //if last day had 1
        dp[2] = Math.max(points[0][0], points[0][1]); //if last day had 2
        dp[3] = Math.max(points[0][0], Math.max(points[0][1], points[0][2])); //no restriction
 
        //for days 1 to n-1
        for (int day = 1; day < n; day++) {
            int[] next = new int[4];
            for (int last = 0; last < 4; last++) { // which activity happend on last day
                int best = 0;
                for (int activity = 0; activity < 3; activity++) {
                    if (activity == last) // we cannot have consecutive
                        continue; // for below we are essentially doing similar to base case
                    best = Math.max(best, points[day][activity] + dp[activity]);
                }
                next[last] = best;
            }
            dp = next;
        }
 
        return dp[3];
    }
 
}

Backlinks