DP 7. Ninja's Training | 2D Dynamic Programming

1. Why Do We Need This? (Problem Statement & Status Quo)

In this problem, a ninja plans an $N$-days training schedule where each day he can perform exactly one of three activities: Running (Activity 0), Fighting Practice (Activity 1), or Learning New Moves (Activity 2).

Each activity yields a specific number of merit points depending on the day. The core constraint is:

The ninja cannot perform the same activity on two consecutive days.

Given an $N \times 3$ 2D matrix of merit points, our objective is to find the maximum total merit points the ninja can earn across all $N$ days.

2. Core Mental Model / Analogy

Real-Life Analogy: Vacation Itinerary Planning

Imagine you are planning a 3-day vacation where every day you have three possible tours to choose from (e.g., Beach, City Museum, Hiking). However, your travel guide imposes a strict rule: You cannot visit the exact same type of attraction on two consecutive days.

If you go hiking on Day 1, you are barred from hiking on Day 2, though you are completely free to hike again on Day 3. You need an itinerary that maximizes your overall enjoyment score without breaking the consecutive activity rule.

3. Naive vs. Better Approach: Why Greedy Fails

The Greedy Temptation

A natural human instinct is to look at the current day, pick the activity with the highest merit points, and move on.

Why Greedy Fails

Greedy algorithms make locally optimal choices without looking ahead. If picking a slightly smaller number today unlocks a massive payoff tomorrow, greedy misses it entirely.

Since greedy fails, we must try all possible ways using recursion and dynamic programming.

4. Step-by-Step Evolution of the Recurrence

To formulate a correct recurrence relation, we follow the standard 3-step dynamic programming checklist:

1. Express the problem in terms of an index: The natural index here is the day (from n - 1 down to 0).
2. Do all stuffs on that index: On any given day, try all valid activities.
3. Optimize according to the goal: Find the maximum merit points (max).

Discovering the Second Parameter: last

When evaluating choices on day i, how do we enforce the rule "cannot perform the same activity as the previous day"?

We need to know what activity was performed on the previous day. Therefore, our recursive function requires two parameters:

• day: The current day index we are deciding for.
• last: The task index (0, 1, or 2) performed on the previous day. (3 represents no task performed yet, used on day n - 1).

5. Complete Recursive Function & Base Case

State Definition

f(day, last): Returns the maximum merit points obtainable from day 0 to day, given that the task performed on day + 1 was last.

Recurrence Code Structure

int f(int day, int last, vector<vector<int>>& points) {
    // Base Case: Day 0
    if (day == 0) {
        int maxi = 0;
        for (int task = 0; task <= 2; task++) {
            if (task != last) {
                maxi = max(maxi, points[0][task]);
            }
        }
        return maxi;
    }

    int maxi = 0;
    // Try all tasks for the current day
    for (int task = 0; task <= 2; task++) {
        if (task != last) {
            int point = points[day][task] + f(day - 1, task, points);
            maxi = max(maxi, point);
        }
    }
    return maxi;
}

6. Recursion Tree & Overlapping Subproblems

When calling f(n - 1, 3), the recursion branches out into multiple choices per day. As N grows larger, identical states (e.g., f(1, 0) or f(1, 2)) are computed repeatedly.

                 f(3, 3)  [Day 3, No previous restriction]
                /    |    \
        f(2, 0)    f(2, 1)   f(2, 2)   [Day 2]
         /    \      ...
    f(1, 1)  f(1, 2) ...              [Day 1 - Overlapping Subproblems!]

Because of these overlapping subproblems, pure recursion results in exponential time complexity $O(3^N)$, necessitating Memoization.

7. Memoization (Top-Down DP)

State Space Analysis

• day ranges from 0 to N - 1 ($N$ states).
• last ranges from 0 to 3 ($4$ states: Tasks 0, 1, 2, and 3 for initial state).
• Total DP Table Size: $N \times 4$.

Memoized Implementation

int f(int day, int last, vector<vector<int>>& points, vector<vector<int>>& dp) {
    if (day == 0) {
        int maxi = 0;
        for (int task = 0; task <= 2; task++) {
            if (task != last) maxi = max(maxi, points[0][task]);
        }
        return maxi;
    }

    if (dp[day][last] != -1) return dp[day][last];

    int maxi = 0;
    for (int task = 0; task <= 2; task++) {
        if (task != last) {
            int point = points[day][task] + f(day - 1, task, points, dp);
            maxi = max(maxi, point);
        }
    }
    return dp[day][last] = maxi;
}

• Time Complexity: $O(N \times 4 \times 3) \approx O(12N) \rightarrow O(N)$
• Space Complexity: $O(N) \text{ (Recursion Stack)} + O(N \times 4) \text{ (DP Table)} \rightarrow O(N)$

8. Tabulation (Bottom-Up DP)

To eliminate recursion stack space, we convert the top-down memoized approach into an iterative bottom-up tabulation approach.

Tabulation Strategy

1. Initialize DP Table: Create a 2D table dp[N][4] initialized to 0.
2. Handle Base Cases (day == 0): Pre-fill the row for day = 0 for all possible last states (0 to 3).
3. Iterate Bottom-Up: Run loops from day = 1 to N - 1 and last = 0 to 3.

Tabulation Code

int ninjaTraining(int n, vector<vector<int>>& points) {
    vector<vector<int>> dp(n, vector<int>(4, 0));

    // Base case filling for Day 0
    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], points[0][1], points[0][2]});

    // Fill for remaining days
    for (int day = 1; day < n; day++) {
        for (int last = 0; last < 4; last++) {
            dp[day][last] = 0;
            for (int task = 0; task <= 2; task++) {
                if (task != last) {
                    int point = points[day][task] + dp[day - 1][task];
                    dp[day][last] = max(dp[day][last], point);
                }
            }
        }
    }

    return dp[n - 1][3];
}

• Time Complexity: $O(N \times 4 \times 3) \rightarrow O(N)$
• Space Complexity: $O(N \times 4) \rightarrow O(N)$ (Recursion stack completely eliminated).

9. Space Optimization

When computing row day, we only ever reference values from the immediate previous row day - 1. We do not need an entire $N \times 4$ matrix. We can reduce our memory footprint to a pair of 4-element arrays (or a single rolling array).

Space-Optimized Implementation

int ninjaTrainingSpaceOptimized(int n, vector<vector<int>>& points) {
    vector<int> prev(4, 0);

    // Base case initialization for Day 0
    prev[0] = max(points[0][1], points[0][2]);
    prev[1] = max(points[0][0], points[0][2]);
    prev[2] = max(points[0][0], points[0][1]);
    prev[3] = max({points[0][0], points[0][1], points[0][2]});

    for (int day = 1; day < n; day++) {
        vector<int> temp(4, 0);
        for (int last = 0; last < 4; last++) {
            for (int task = 0; task <= 2; task++) {
                if (task != last) {
                    temp[last] = max(temp[last], points[day][task] + prev[task]);
                }
            }
        }
        prev = temp; // Move to the next day
    }

    return prev[3];
}

• Time Complexity: $O(N \times 4 \times 3) \rightarrow O(N)$
• Space Complexity: $O(4) \rightarrow O(1)$ (Constant auxiliary space).

10. Summary and Key Takeaways

• Greedy Fails: Local optimal choices (taking maximum merit points blindly on day 0) fail when future constraints block superior cumulative paths.
• State Representation: Two parameters are essential: day (tracking progression) and last (enforcing the non-consecutive task rule).
• Base Case Design: Day 0 evaluates maximum points possible given the restriction imposed by last.
• Memoization Strategy: An $N \times 4$ DP table effectively eliminates overlapping subproblems.
• Tabulation Advantage: Bottom-up computation removes recursion overhead and prevents stack overflow for large inputs.
• Space Optimization Breakthrough: Because state transitions only depend on the previous row (day - 1), space complexity drops from $O(N)$ down to strict $O(1)$ constant space.