Ninja's Training: Dynamic Programming for Maximum Points

80.2k
0

A matrix points describes merit points for n training days and three available activities. Each row represents one day, while columns 0, 1, and 2 represent running, fighting practice, and learning new moves.

Select exactly one activity per day. Consecutive days cannot use the same activity. Return the maximum total merit points across the complete schedule.

Example 1

Input: points = [[1, 2, 5], [3, 1, 1], [3, 3, 3]]
Output: 11
Explanation: Choose points[0][2] = 5 on day 0, points[1][0] = 3 on day 1, and points[2][1] = 3 on day 2. The chosen activity indices are 2, 0, and 1, so no two consecutive days use the same activity. The maximum total is 5 + 3 + 3 = 11.

Example 2

Input: points = [[8, 3, 5]]
Output: 8
Explanation: A single training day has no neighboring-day restriction. Activity index 0 gives the largest available score, 8.

Recursion

A valid schedule makes one small choice per day: select an activity different from the neighboring day's activity. Starting from the final day keeps the first choice open because no later activity exists. Every selected activity leaves the same scheduling problem for the remaining earlier days.

The state solve(day, last) returns the best score from day 0 through day, with activity last forbidden on day. Sentinel value 3 represents no forbidden activity for the initial call. Direct recursion follows every valid branch and reveals the repeated decision clearly.

Algorithm

  • Define solve(day, last) so the state records the active day and the activity blocked by the next day, preserving the consecutive-day rule during backward movement.

  • Begin with solve(n - 1, 3) because sentinel value 3 leaves all three activities available on the final day.

  • Inspect every activity on day 0 except last, then return the largest allowed score because no earlier day remains.

  • Try all three activities on every later day and skip last because matching the neighboring activity would create an invalid schedule.

  • Add points[day][activity] to solve(day - 1, activity) so the chosen activity becomes the restriction for the preceding day.

  • Keep the largest candidate across all valid activities because the goal requires the highest complete schedule score.

  • Return the largest candidate to the preceding recursive state, allowing every earlier choice to compare complete valid totals.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the best score for one recursive state.
int solve(int day, int last, vector<vector<int>>& points) {
// Stop at day zero because no earlier day remains.
if (day == 0) {
int best = 0;
// Check every activity to find the best valid start.
for (int activity = 0; activity < 3; activity++) {
// Skip the blocked activity to prevent repetition.
if (activity != last) {
// Keep the strongest allowed first-day score.
best = max(best, points[0][activity]);
}
}
// Return the best valid score for the first day.
return best;
}
int best = 0;
// Explore every activity because each choice can win.
for (int activity = 0; activity < 3; activity++) {
// Skip the blocked activity to preserve validity.
if (activity != last) {
// Add the chosen score to the earlier schedule.
int candidate = points[day][activity]
+ solve(day - 1, activity, points);
// Keep the largest complete valid total.
best = max(best, candidate);
}
}
// Return the strongest schedule for the state.
return best;
}
public:
// Returns the maximum merit points for all days.
int ninjaTraining(vector<vector<int>>& points) {
int n = points.size();
// Sentinel three leaves the final day unrestricted.
return solve(n - 1, 3, points);
}
};
// Driver code
int main() {
vector<vector<int>> points = {{1, 2, 5}, {3, 1, 1}, {3, 3, 3}};
Solution obj;
cout << obj.ninjaTraining(points) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of training days, because each non-base state can branch into two valid activity choices after the first activity is selected.

Space Complexity: O(N), because the recursion stack can contain at most one active call for each training day.

Memoization

Direct recursion reaches identical (day, last) states through different activity sequences. Every repeated state produces the same answer, so recalculating a complete subtree adds work without adding information.

A two-dimensional array named dp stores one answer for every day and forbidden activity. A saved value turns an entire repeated subtree into a constant-time lookup. The recursive choice and state meaning remain unchanged.

Algorithm

  • Keep the recursive state solve(day, last) unchanged so memoization optimizes repeated work without altering the scheduling decision.

  • Create dp with n rows and four columns, filled with -1, so every untouched entry clearly marks an uncalculated state.

  • Start from solve(n - 1, 3) because sentinel value 3 leaves the final day free from an activity restriction.

  • Return dp[day][last] immediately after finding a stored value, avoiding another traversal of the same recursive subtree.

  • Evaluate day 0 by selecting the largest activity score different from last, then store the base answer so later calls can reuse the completed state.

  • Explore every allowed activity on later days and combine the current score with solve(day - 1, activity), preserving the original recurrence.

  • Store and return the largest candidate in dp[day][last], making the completed state reusable across later branches.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds and stores the best score for one state.
int solve(
int day,
int last,
vector<vector<int>>& points,
vector<vector<int>>& dp
) {
// Reuse a saved answer to avoid repeated work.
if (dp[day][last] != -1) {
return dp[day][last];
}
// Stop at day zero because no earlier day remains.
if (day == 0) {
int best = 0;
// Check every activity to find the best valid start.
for (int activity = 0; activity < 3; activity++) {
// Skip the blocked activity to prevent repetition.
if (activity != last) {
// Keep the strongest allowed first-day score.
best = max(best, points[0][activity]);
}
}
// Store the base answer for later cache hits.
dp[day][last] = best;
return dp[day][last];
}
int best = 0;
// Explore every activity because each choice can win.
for (int activity = 0; activity < 3; activity++) {
// Skip the blocked activity to preserve validity.
if (activity != last) {
// Add the chosen score to the cached subproblem.
int candidate = points[day][activity]
+ solve(day - 1, activity, points, dp);
// Keep the largest complete valid total.
best = max(best, candidate);
}
}
// Store the completed state before returning.
dp[day][last] = best;
return dp[day][last];
}
public:
// Returns the maximum merit points for all days.
int ninjaTraining(vector<vector<int>>& points) {
int n = points.size();
// Minus one marks every state as uncalculated.
vector<vector<int>> dp(n, vector<int>(4, -1));
// Sentinel three leaves the final day unrestricted.
return solve(n - 1, 3, points, dp);
}
};
// Driver code
int main() {
vector<vector<int>> points = {{1, 2, 5}, {3, 1, 1}, {3, 3, 3}};
Solution obj;
cout << obj.ninjaTraining(points) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of training days, because each day has at most four states and each state checks only three activities.

Space Complexity: O(N), because the N × 4 DP cache and the recursion stack of depth at most N both require linear space.

Tabulation

Memoization requests states from the final day and solves earlier states on demand. Tabulation reverses the flow: day 0 is filled first, followed by each later day. Every required earlier answer is already available before a new row begins.

The table dp[day][last] keeps the same meaning as the recursive state. Four values are stored per day because three values describe a forbidden activity and value 3 describes no restriction. Bottom-up order removes recursive calls while preserving the same choices.

Algorithm

  • Create a table dp with n rows and four columns so every recursive (day, last) state has one iterative position.

  • Fill the four states for day 0 with the best score outside each forbidden activity so every later transition begins from a complete base row.

  • Move from day 1 through day n - 1 because every current state depends only on values from the preceding row.

  • Examine all four last values for each day so restricted states and the unrestricted sentinel state remain available.

  • Try each activity different from last because equal values would repeat an activity across neighboring days.

  • Add the current activity score to dp[day - 1][activity] because the selected activity becomes the preceding row's restriction.

  • Store the largest candidate in dp[day][last] so every state keeps the best total, then return dp[n - 1][3] because sentinel value 3 removes the outer restriction.

Dry Run

Ninjas Training Tabulation

Ninjas Training Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum merit points with tabulation.
int ninjaTraining(vector<vector<int>>& points) {
int n = points.size();
// Four columns preserve every forbidden choice.
vector<vector<int>> dp(n, vector<int>(4, 0));
// Build the base row from valid first-day choices.
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],
max(points[0][1], points[0][2]));
// Move forward because every earlier row is ready.
for (int day = 1; day < n; day++) {
// Calculate all four forbidden-activity states.
for (int last = 0; last < 4; last++) {
// Try every activity because any choice can win.
for (int activity = 0; activity < 3; activity++) {
// Skip repetition to keep the schedule valid.
if (activity != last) {
// Add the score to the matching prior state.
int candidate = points[day][activity]
+ dp[day - 1][activity];
// Keep the largest total for the state.
dp[day][last] = max(
dp[day][last], candidate
);
}
}
}
}
// Sentinel three represents no final restriction.
return dp[n - 1][3];
}
};
// Driver code
int main() {
vector<vector<int>> points = {{1, 2, 5}, {3, 1, 1}, {3, 3, 3}};
Solution obj;
cout << obj.ninjaTraining(points) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of training days, because each day computes four states and each state checks three activities, which is constant work.

Space Complexity: O(N), because the DP table stores four values for each of the N days, while the iterative approach uses no recursion stack.

Space Optimization

Every tabulation transition reads only the preceding row. Rows older than one day never participate in a later calculation, so a full n-row table stores unnecessary history.

An array named previous holds the completed row, while current collects the next row. Every current value must be calculated before the row shift. Afterward, current becomes previous, preserving exactly the data needed by the next day.

Algorithm

  • Store the four day 0 states in previous because every later calculation needs only the immediately preceding row.

  • Move from day 1 through day n - 1 because every state depends only on the completed preceding row.

  • Create a fresh four-value current row for each day so unfinished values cannot overwrite required values in previous.

  • Examine every last value and every activity different from last, preserving all four state meanings and the consecutive-day restriction.

  • Add points[day][activity] to previous[activity] because the chosen activity identifies the required state from the preceding day.

  • Keep the largest candidate in current[last] so no unfinished state replaces required values from previous.

  • Shift current into previous only after the full row is ready because every next-day transition needs a complete row, then return previous[3] as the unrestricted answer.

Dry Run

Ninjas Training Space Optimization

Ninjas Training Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum score with two small rows.
int ninjaTraining(vector<vector<int>>& points) {
int n = points.size();
// Previous stores every first-day state.
vector<int> previous(4, 0);
previous[0] = max(points[0][1], points[0][2]);
previous[1] = max(points[0][0], points[0][2]);
previous[2] = max(points[0][0], points[0][1]);
previous[3] = max(points[0][0],
max(points[0][1], points[0][2]));
// Move forward because only the prior row is needed.
for (int day = 1; day < n; day++) {
vector<int> current(4, 0);
// Calculate every current state before the shift.
for (int last = 0; last < 4; last++) {
// Try every activity because any choice can win.
for (int activity = 0; activity < 3; activity++) {
// Skip repetition to keep the schedule valid.
if (activity != last) {
// Add the score to the matching prior state.
int candidate = points[day][activity]
+ previous[activity];
// Keep the largest total for the state.
current[last] = max(
current[last], candidate
);
}
}
}
// Shift only after every current state is ready.
previous = current;
}
// Sentinel three represents no final restriction.
return previous[3];
}
};
// Driver code
int main() {
vector<vector<int>> points = {{1, 2, 5}, {3, 1, 1}, {3, 3, 3}};
Solution obj;
cout << obj.ninjaTraining(points) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of days, because each day computes four states and each state checks three activities, which is constant work.

Space Complexity: O(1), because only two arrays of four values are maintained, independent of N.

Interview follow-up Questions

No. State value 3 acts only as a sentinel for no forbidden activity. Real activity indices remain 0, 1, and 2.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Input: nums = [1, 16, 7, 8, 4] Output: [1, 4, 8, 16] Explanation: Every pair inside [1, 4, 8, 16] satisfies the divisibility rule. The value 7 cannot join the chain because no other chain value div...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0