Ninja's training
On a day , a Ninja can train for one exercise out of 3, and whatever he did yesterday couldn't be done today return maximum credit
of three activities - running, stealth training, or fighting practice. The same activity cannot be done on two consecutive days and the ninja earns a specific number of merit points, based on the activity and the given day.
Given a n x 3-sized matrix, where matrix[i][0], matrix[i][1], and matrix[i][2], represent the merit points associated with running, stealth and fighting practice, on the (i+1)th day respectively. Return the maximum possible merit points that the ninja can earn.
Example 1: Input: matrix = [[10, 40, 70], [20, 50, 80], [30, 60, 90]]
Output: 210
Explanation:
Day 1: fighting practice = 70
Day 2: stealth training = 50
Day 3: fighting practice = 90
Total = 70 + 50 + 90 = 210
This gives the optimal points.
Example 2: Input: matrix = [[70, 40, 10], [180, 20, 5], [200, 60, 30]]
Output: 290
Explanation:
Day 1: running = 70
Day 2: stealth training = 20
Day 3: running = 200
Total = 70 + 20 + 200 = 290
This gives the optimal points.
Solution
Brute Force here we'll keep track of current day and last value we have used to avoid using that again. For the base case we'll find max of that row except last value. and for all other rows we'll find trace all possible columns and return which ever gives us largest value after entire calculation.
ninjaTraining(matrix) {
let n = matrix.length - 1;
function recurr(day, last) {
if (day === 0) {
let best = 0;
for (let activity = 0; activity < 3; activity++) {
if (activity === last) continue;
best = Math.max(best, matrix[day][activity]);
}
return best;
}
let best = 0;
for (let activity = 0; activity < 3; activity++) {
if (activity === last) continue;
let curr = matrix[day][activity] + recurr(day - 1, activity);
best = Math.max(curr, best);
}
return best;
}
return recurr(n, 3);
}
Memorization
make sure dp is a 2d array of day , last
ninjaTraining(matrix) {
let n = matrix.length - 1;
const dp = Array.from({ length: matrix.length }, () => Array(4).fill(-1));
function recurr(day, last, dp) {
if (dp[day][last] !== -1) {
return dp[day][last];
}
if (day === 0) {
let best = 0;
for (let activity = 0; activity < 3; activity++) {
if (activity === last) continue;
best = Math.max(best, matrix[day][activity]);
}
dp[day][last] = best;
return dp[day][last];
}
let best = 0;
for (let activity = 0; activity < 3; activity++) {
if (activity === last) continue;
let curr = matrix[day][activity] + recurr(day - 1, activity, dp);
best = Math.max(curr, best);
}
dp[day][last] = best;
return dp[day][last];
}
return recurr(n, 3, dp);
}
Tabulation we'll start by generating base cases were we'll describe what we want in 0th row if day has certain and last has certain value.
Note that we are considering activity as 3 but last as 4 because when there is only one row we don't want to skip anything.
then we'll apply a loop for each day from 1 to n we'll skip each last value from 0-3 for each last value we'll check for all the activity from 0-2 and find the max value.
ninjaTraining(points) {
const n = points.length;
// Four columns preserve every forbidden choice.
const dp = Array.from({ length: n }, () => Array(4).fill(0));
// Build the base row from valid first-day choices.
dp[0][0] = Math.max(points[0][1], points[0][2]);
dp[0][1] = Math.max(points[0][0], points[0][2]);
dp[0][2] = Math.max(points[0][0], points[0][1]);
dp[0][3] = Math.max(
points[0][0], points[0][1], points[0][2]
);
// Move forward because every earlier row is ready.
for (let day = 1; day < n; day++) {
// Calculate all four forbidden-activity states.
for (let last = 0; last < 4; last++) {
// Try every activity because any choice can win.
for (let activity = 0; activity < 3; activity++) {
// Skip repetition to keep the schedule valid.
if (activity !== last) {
// Add the score to the matching prior state.
const candidate = points[day][activity]
+ dp[day - 1][activity];
// Keep the largest total for the state.
dp[day][last] = Math.max(
dp[day][last], candidate
);
}
}
}
}
// Sentinel three represents no final restriction.
return dp[n - 1][3];
}
}
Space Optimization
ninjaTraining(points) {
const n = points.length;
// Previous stores every first-day state.
let previous = Array(4).fill(0);
previous[0] = Math.max(points[0][1], points[0][2]);
previous[1] = Math.max(points[0][0], points[0][2]);
previous[2] = Math.max(points[0][0], points[0][1]);
previous[3] = Math.max(
points[0][0], points[0][1], points[0][2]
);
// Move forward because only the prior row is needed.
for (let day = 1; day < n; day++) {
const current = Array(4).fill(0);
// Calculate every current state before the shift.
for (let last = 0; last < 4; last++) {
// Try every activity because any choice can win.
for (let activity = 0; activity < 3; activity++) {
// Skip repetition to keep the schedule valid.
if (activity !== last) {
// Add the score to the matching prior state.
const candidate = points[day][activity]
+ previous[activity];
// Keep the largest total for the state.
current[last] = Math.max(
current[last], candidate
);
}
}
}
// Shift only after every current state is ready.
previous = current;
}
// Sentinel three represents no final restriction.
return previous[3];
}