Geek’s Training | 2D Dynamic Programming | GFG Practice

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 .

Here’s the [Problem Link] to begin with.

Example:

Input: arr[]= [[1, 2, 5], [3, 1, 1], [3, 3, 3]]
Output: 11
Explanation: Geek will learn a new move and earn 5 point then on second day he will do running and earn 3 point and on third day he will do fighting and earn 3 points so, maximum merit point will be 11.

Input: arr[]= [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
Output: 6
Explanation: Geek can perform any activity each day while adhering to the constraints, in order to maximize his total merit points as 6.

Input: arr[]= [[4, 2, 6]]
Output: 6
Explanation: Geek will learn a new move to make his merit points as 6.

Constraint:
1 <=  n <= 10⁵   
1 <=  arr[i][j] <= 100

Solution 1: Brute Force Approach (Pure Recursion)

Intuition

Think recursively: For each day, try all possible tasks that differ from the last day’s task, add the points, and recurse to the previous day. At day 0, pick the max possible task != last. This explores all valid paths backward, choosing the maximum at each step.

Detailed Approach

• Base Case: If day == 0, return max of arr[i] where i != last.
• Recursive Case: For current day, loop over tasks i (0-2), if i != last, compute arr[day][i] + solve(day-1, i), and take the global max.
• ‘last’ starts as 3 (no previous constraint).
• Explores exponential paths due to overlaps.

Code

class Solution:
    def solve(self, day, last, arr):
        # Base case: Day 0, pick max task != last
        if day == 0:
            maxi = 0
            for i in range(0, 3):
                if last != i:
                    maxi = max(maxi, arr[day][i])
            return maxi
        # For current day, try all valid tasks
        maxi = 0
        for i in range(0, 3):
            if last != i:
                maxi = max(maxi, arr[day][i] + self.solve(day - 1, i, arr))
        return maxi

    def maximumPoints(self, arr):
        n = len(arr)
        # Start from last day with no previous task (last=3)
        return self.solve(n - 1, 3, arr)

Code Explanation

The solve function computes max points from day to 0, given the last task. It loops over possible tasks for the current day (skipping if same as last), recurses with the chosen task as new last, and accumulates max. The main function starts from day n-1 with last=3 (dummy).

Time and Space Complexity

• Precise: Time O(3^n) (up to 3 choices per day), Space O(n) (recursion depth).
• Simplified: Time exponential O(3^n), slow for large n; Space O(n) from stack.

Simplifying It

Like trying every possible training schedule without remembering past choices, intuitive but repeats a lot of work!

Solution 2: Memoization Approach (Top-Down DP)

Intuition

Recursion recomputes subproblems (e.g., points from day 5 with last=1 multiple times). Use a DP table [day][last] to store results, checking before computing.

Detailed Approach

• DP: n x 4 array (last 0-3), init -1.
• If dp[day][last] != -1, return it.
• Else, compute as recursion, store in dp.
• Reduces to linear by caching.

Code

class Solution:
    def solve(self, day, last, arr, dp):
        # Check memo
        if dp[day][last] != -1:
            return dp[day][last]
        # Base case for day 0
        if day == 0:
            maxi = 0
            for i in range(0, 3):
                if last != i:
                    maxi = max(maxi, arr[day][i])
            return maxi
        # Compute max for current day
        maxi = 0
        for i in range(0, 3):
            if last != i:
                maxi = max(maxi, arr[day][i] + self.solve(day - 1, i, arr, dp))
        # Store in memo
        dp[day][last] = maxi
        return dp[day][last]

    def maximumPoints(self, arr):
        n = len(arr)
        # DP table: n days x 4 last tasks
        dp = [[-1 for _ in range(4)] for _ in range(n)]
        return self.solve(n - 1, 3, arr, dp)

Code Explanation

Adds dp check/store to recursion. Computes only once per state (day, last), reusing for efficiency.

Time and Space Complexity

• Precise: Time O(n * 4 * 3) = O(n), Space O(n*4) + O(n) stack.
• Simplified: Time O(n), Space O(n) (table + stack).

Simplifying It

Now with a notebook for each day and previous choice, look up answers instead of recalculating!

Solution 3: Tabulation Approach (Bottom-Up DP)

Intuition

Build from day 0 upward. For each day and possible last, compute max by trying valid tasks, using previous day’s dp.

Detailed Approach

• DP n x 4.
• Init day 0: dp[last] = max valid tasks != last (special for last=3: overall max).
• For each day 1 to n-1, for each last 0-3, max over i != last: arr[day][i] + dp[day-1][i].
• Return dp[n-1].

Code

class Solution:
    def maximumPoints(self, arr):
        n = len(arr)
        # DP table: n days x 4 last tasks
        dp = [[-1 for _ in range(4)] for _ in range(n)]
        # Init day 0 for each possible last
        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], arr[0][1], arr[0][2])
        # Fill for each day
        for day in range(1, n):
            for last in range(0, 4):
                maxi = 0
                for i in range(0, 3):
                    if i != last:
                        maxi = max(maxi, arr[day][i] + dp[day - 1][i])
                dp[day][last] = maxi
        return dp[n - 1][3]

Code Explanation

Fills dp bottom-up, ensuring each cell uses previous day’s values. No recursion.

Time and Space Complexity

• Precise: Time O(n * 4 * 3) = O(n), Space O(n*4).
• Simplified: Time O(n), Space O(n).

Simplifying It

Like filling a schedule table day by day, building on yesterday’s best choices!

Solution 4: Tabulation (Space Optimization) Approach (Optimal)

Intuition

Since we only need previous day’s dp, use two 1D arrays: prev and curr. Update curr based on prev, then set prev = curr.

Detailed Approach

• Init prev as day 0 values.
• For each day, compute curr similarly.
• Copy curr to prev.
• O(1) space extra.

Code

class Solution:
    def maximumPoints(self, arr):
        n = len(arr)
        # Prev row for space opt
        prev = [-1 for _ in range(4)]
        # Init for day 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], arr[0][1], arr[0][2])
        # For each day
        for day in range(1, n):
            curr = [-1 for _ in range(4)]
            for last in range(0, 4):
                maxi = 0
                for i in range(0, 3):
                    if i != last:
                        maxi = max(maxi, arr[day][i] + prev[i])
                curr[last] = maxi
            # Update prev to curr
            prev = curr.copy()
        return prev[3]

Code Explanation

Uses prev array for previous day, computes curr, updates. Minimizes space.

Time and Space Complexity

• Precise: Time O(n * 4 * 3) = O(n), Space O(4) = O(1).
• Simplified: Time O(n), Space O(1).

Simplifying It

Like keeping only yesterday’s notes, efficient and clutter-free!

Summary

Overall Conclusion

The Geek’s Training problem sharpens your DP state management skills. Start recursive for understanding, optimize with memo/tabulation, and ace interviews with space efficiency. Practice similar problems on GFG or LeetCode.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.