~/DHRUVUpskilling
← board/DSA/Dynamic Programming/dsa-dynamic-programming-07
Solved·02 Oct

Ninja's training

DifficultyMedium
PatternDynamic Programming
TrackDSA
tl;dr

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

full write-up

Ninja's Training

Problem Statement

A ninja is training over several days. On each day, the ninja can choose to do one 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, depending on the activity and the day.

You are given an n x 3 matrix, where matrix[i][0], matrix[i][1], and matrix[i][2] represent the merit points for running, stealth training, and fighting practice, respectively, on day i + 1.

Return the maximum possible merit points the ninja can earn.

Examples

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

We keep track of the current day and the last activity used, so we never repeat the same activity two days in a row.

  • For the base case (the very first day, day === 0), we look at that day's row and take the largest value, excluding whichever activity was marked as "last" (not allowed).
  • For every other day, we try every allowed activity (anything except the "last" one), add its points to the best result from the previous day (with this activity now marked as "last" for that call), and keep whichever choice gives the largest total.
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);
}

Memoization (Top-Down)

We use the same recursive logic, but store results in a dp grid so we never repeat the same calculation. The dp grid is indexed by day and last activity used.

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 (Bottom-Up)

We start by filling in the base row — what the best score looks like on day 0, depending on which activity is considered "forbidden" (last used). Then, we move forward day by day, filling in each day's results based on the day before it.

  • For each day, and for each possible "last activity" restriction (0 to 3), we try every valid activity (0 to 2) that isn't the forbidden one, and take whichever gives the largest total.
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

Since each day's results only depend on the previous day's results, we don't need to store the entire grid — just the previous row, which we update as we move forward.

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];
}
Ninja's training — pattern notes — Dhruv Parmar