Ninja's Training
2D/3D DP and Grids DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Introduction to 2D Dynamic Programming using the Ninja Training Problem, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Greedy Algorithm, Time Complexity, Space Complexity, constraints, dynamic programming, memoization, state management, tabulation, space optimization, recursion, 1D & 2D DP, DP State Management, Problem Solving Techniques.
Ninja Training A ninja has an 'N' day training schedule. On each day, the ninja must perform exactly one of three activities: Running, Fighting Practice, or Learning New Moves. Each activity has an associated merit point value for that specific day. The crucial constraint is that the same activity cannot be performed on two consecutive days. Your task is to find the maximum total merit points the ninja can attain over the 'N' days. Input Specification The input consists of: An integer N, representing the number of training days. A 2D array POINTS of size N x 3, where POINTS[i][j] denotes the merit points for performing activity j (0 for Running, 1 for Fighting Practice, 2 for Learning New Moves) on day i. Output Specification Return a single integer, the maximum merit points the ninja can earn. Constraints 1 <= N <= 10^5 0 <= POINTS[i][j] <= 1000 Sample Test Cases Sample Input 1: Sample Output 1: Explanation: One optimal path is: Day 0: Activity 2 (Learning New Moves) 70 points Day 1: Activity 1 (Fighting Practice) 50 points Day 2: Activity 2 (Learning New Moves) 90 points Total points = 70 + 50 + 90 = 210. Another optimal path is: Day 0: Activity 2 (Learning New Moves) 70 points Day 1: Activity 0 (Running) 20 points Day 2: Activity 2 (Learning New Moves) 90 points Total points = 70 + 20 + 90 = 180 (Not optimal). Optimal selection: Day 0: Activity 2 (70 points) Day 1: Activity 1 (50 points) Day 2: Activity 2 (90 points) Total: 70 + 50 + 90 = 210 (Note: The example in the original content for greedy was 50+11 = 61 which seems to be from a different set of points not provided in the problem statement itself, so I'm sticking to the one that gives 210. The 10, 100 combination yielding 110 was also from a different set. The explanation for greedy failure is general and can be kept.)