Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Geek’s Training | 2D Dynamic Programming | GFG Practice
    Data Structures & Algorithms

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

    codeanddebugBy codeanddebug30 July 2025No Comments7 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve geeks training
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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 <= 105   
    1 <=  arr[i][j] <= 100

    Contents:
     [show]
    • Solution 1: Brute Force Approach (Pure Recursion)
      • Intuition
      • Detailed Approach
      • Code
      • Code Explanation
      • Time and Space Complexity
      • Simplifying It
    • Solution 2: Memoization Approach (Top-Down DP)
      • Intuition
      • Detailed Approach
      • Code
      • Code Explanation
      • Time and Space Complexity
      • Simplifying It
    • Solution 3: Tabulation Approach (Bottom-Up DP)
      • Intuition
      • Detailed Approach
      • Code
      • Code Explanation
      • Time and Space Complexity
      • Simplifying It
    • Solution 4: Tabulation (Space Optimization) Approach (Optimal)
      • Intuition
      • Detailed Approach
      • Code
      • Code Explanation
      • Time and Space Complexity
      • Simplifying It
    • Summary
    • Overall Conclusion

    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

    ApproachTimeSpaceDifficultyBest For
    Recursion (Brute Force)O(3^n)O(n)EasyIntuition building
    Memoization (Top-Down DP)O(n)O(n)MediumCaching practice
    Tabulation (Bottom-Up DP)O(n)O(n)MediumIterative reliability
    Space-Optimized TabulationO(n)O(1)Medium-HardOptimal performance

    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.

    Join our Advance DSA COURSE

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

    Dynamic Programming on 2D Arrays Medium
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleHouse Robber II | Leetcode 213 | All 4 Solutions
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    House Robber II | Leetcode 213 | All 4 Solutions

    30 July 2025
    Data Structures & Algorithms

    House Robber | Leetcode 198 | Brute Force and Optimal Solutions

    29 July 2025
    Data Structures & Algorithms

    Frog Jump | GFG Practice | Dynamic Programming

    29 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (163)
      • Beginner (62)
      • Expert (39)
      • Intermediate (62)
    • Uncategorised (1)
    Recent Posts

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

    30 July 2025

    House Robber II | Leetcode 213 | All 4 Solutions

    30 July 2025

    House Robber | Leetcode 198 | Brute Force and Optimal Solutions

    29 July 2025

    Frog Jump | GFG Practice | Dynamic Programming

    29 July 2025

    Implement Stack using Queues | Leetcode 225 | Complete Python Code

    26 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.