DSA
Ninja Training
4 approaches incl. A. Recursive, B. Memoization, B. Tabulation, and more. Optimal — Time O(n * 4 * 3), Space O(4).
Geek is going for a training program for n days. He can perform any of these activities: Running, Fighting, and Learning Practice. Each activity has some point on each day. As Geek wants to improve all his skills, he can't do the same activity on two consecutive days. Given a 2D array arr[][] of size n where arr[i][0], arr[i][1], and arr[i][2] represent the merit points for Running, Fighting, and Learning on the i-th day, determine the maximum total merit points Geek can achieve .
Practice Link
Implementation#
A. Recursive Approach#
For each day we try all three activities, skipping whichever was chosen the previous day. The state (day, lastChoice) fully captures what we need: which day we are on and which activity to avoid. Without caching, the same state is recomputed in many branches, giving exponential time.
class Solution {
public:
int maximumPointsUtil(vector<vector<int>>& arr, int day, int lastChoice)
{
if(day<0)
{
return 0;
}
int maxi = 0;
for(int i=0;i<3;i++)
{
if(i!=lastChoice)
{
maxi = max(maxi, arr[day][i] + maximumPointsUtil(arr, day-1, i));
}
}
return maxi;
}
int maximumPoints(vector<vector<int>>& arr) {
return maximumPointsUtil(arr, arr.size()-1, -1);
}
};
Time Limit Exceeded
B. Memoization#
Cache results in memo[day][lastChoice] — a n × 4 table (4 because lastChoice can be 0, 1, 2, or 3 for "no previous constraint"). Each of the n × 4 states is evaluated once with an inner loop of 3 iterations, giving O(n × 4 × 3) ≈ O(n) time.
class Solution {
public:
int maximumPointsUtil(vector<vector<int>>& arr, int day, int lastChoice, vector<vector<int>> &memo)
{
if(day<0)
{
return 0;
}
if(memo[day][lastChoice]!= -1)
return memo[day][lastChoice];
int maxi = 0;
for(int i=0;i<3;i++)
{
if(i!=lastChoice)
{
maxi = max(maxi, arr[day][i] + maximumPointsUtil(arr, day-1, i, memo));
}
}
return memo[day][lastChoice] = maxi;
}
int maximumPoints(vector<vector<int>>& arr) {
vector<vector<int>> memo(arr.size(), vector<int>(4, -1));
return maximumPointsUtil(arr, arr.size()-1, 3, memo);
}
};
Time Complexity - O(n * 4 * 3), There are N*4 states and for every state, we are running a for loop iterating three times.
Space Complexity - O(N) + O(N4), We are using a recursion stack space(O(N)) and a 2D array (again O(N4)). Therefore total space complexity will be O(N) + O(N) ≈ O(N)
C. Tabulation Solution#
Build the table bottom-up. Initialize day 0 by hand (for each lastChoice, pick the best activity that's not forbidden). For subsequent days, dp[day][lastChoice] = maximum points by choosing any task != lastChoice on this day plus dp[day-1][task]. This iterative fill eliminates the recursion stack.
cclass Solution {
public:
int maximumPoints(vector<vector<int>>& arr) {
vector<vector<int>> dp(arr.size(), vector<int>(4, 0));
dp[0][0] = max(arr[0][1], arr[0][2]);
dp[0][1] = max(arr[0][0], arr[0][2]);
dp[0][2] = max(arr[0][0], arr[0][1]);
dp[0][3] = max(arr[0][0], max(arr[0][1], arr[0][2]));
for(int day=1;day<arr.size();day++)
{
for(int lastChoice=0;lastChoice<4;lastChoice++)
{
dp[day][lastChoice] = 0;
for(int task = 0;task<3;task++)
{
if(lastChoice != task)
{
int currPoints = arr[day][task] + dp[day-1][task];
dp[day][lastChoice] = max(dp[day][lastChoice], currPoints);
}
}
}
}
return dp[arr.size()-1][3];
}
};
Time Complexity - O(n * 4 * 3)
Space Complexity - O(N * 4)
Tabulation: Space Optimized#
Each day's row depends only on the previous day's row. Replace the full n × 4 table with two 4-element arrays (prev and curr). After each day, set prev = curr. Space drops from O(n × 4) to O(4) — a constant — with identical time.
class Solution {
public:
int maximumPoints(vector<vector<int>>& arr) {
vector<int> prev(4, 0);
prev[0] = max(arr[0][1], arr[0][2]);
prev[1] = max(arr[0][0], arr[0][2]);
prev[2] = max(arr[0][0], arr[0][1]);
prev[3] = max(arr[0][0], max(arr[0][1], arr[0][2]));
for(int day=1;day<arr.size();day++)
{
vector<int> curr(4, 0);
for(int lastChoice=0;lastChoice<4;lastChoice++)
{
curr[lastChoice] = 0;
for(int task = 0;task<3;task++)
{
if(lastChoice != task)
{
curr[lastChoice] = max(curr[lastChoice], arr[day][task] + prev[task]);
}
}
}
prev = curr;
}
return prev[3];
}
};
Time Complexity - O(n * 4 * 3)
Space Complexity - O(4)