Start practising

Geek's Training

Medium Dynamic Programming 2D DP - max/min of last row Original on GeeksforGeeks

Geek's Training is a medium dynamic programming problem solved with the 2d dp - max/min of last row pattern. The best approach, optimal (dp over days with 3 states), runs in O(n · 9) time and O(1) space. Below are 2 approaches in Java, from recursion with the last activity up.

Problem

Over n days, each day you do one of three activities, earning arr[day][activity] points. You cannot repeat the same activity on consecutive days. Return the maximum total points.

Examples

Example 1

Input
arr = [[1,2,5],[3,1,1],[3,3,3]]
Output
11
Why
Day 1 activity 2 (5), day 2 activity 0 (3), day 3 activity 1 or 2 (3).

Example 2

Input
arr = [[1,1,1],[2,2,2],[3,3,3]]
Output
6

Constraints

  • 1 <= n <= 10^5; 3 activities per day; points 1 to 100.
  • You cannot do the same activity on two consecutive days.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Recursion with the last activityO(3 · 2ⁿ)O(n)
Optimal (DP over days with 3 states)O(n · 9)O(1)

1Recursion with the last activity

TimeO(3 · 2ⁿ)
SpaceO(n)

solve(day, last) = the best over activities a != last of points[day][a] + solve(day - 1, a).

  1. Base day 0: max over a != last.
Java
class Solution {
    public int maximumPoints(int[][] arr) {
        return solve(arr, arr.length - 1, 3);
    }

    private int solve(int[][] p, int day, int last) {
        int best = 0;
        for (int a = 0; a < 3; a++) {
            if (a == last) continue;
            int v = p[day][a] + (day == 0 ? 0 : solve(p, day - 1, a));
            best = Math.max(best, v);
        }
        return best;
    }
}

2Optimal (DP over days with 3 states)

TimeO(n · 9)
SpaceO(1)

prev[a] = best total up to yesterday if yesterday's activity was a. Today's cur[a] = points[day][a] + max of prev over the other two activities. The answer is max over the last day.

  1. prev = points[0].
  2. cur[a] = p[d][a] + max(prev[b]) for b != a.
  3. Return max(prev) at the end.
Java
class Solution {
    public int maximumPoints(int[][] arr) {
        int[] prev = arr[0].clone();
        for (int d = 1; d < arr.length; d++) {
            int[] cur = new int[3];
            for (int a = 0; a < 3; a++) {
                int best = 0;
                for (int b = 0; b < 3; b++) if (b != a) best = Math.max(best, prev[b]);
                cur[a] = arr[d][a] + best;
            }
            prev = cur;
        }
        return Math.max(prev[0], Math.max(prev[1], prev[2]));
    }
}

Edge cases to test

  • A single day (take the max)

Hints

Hint 1

The state is (day, last activity). dp[d][a] = best total up to day d if day d's activity is a.

FAQ

What is the best time complexity for Geek's Training?

Optimal (DP over days with 3 states) runs in O(n · 9) time and O(1) extra space.

Which pattern does Geek's Training use?

It is a dynamic programming problem that uses the 2d dp - max/min of last row pattern. Other problems with the same pattern: Minimum Falling Path Sum, Triangle.

Is there a brute force solution for Geek's Training?

Yes. Recursion with the last activity takes O(3 · 2ⁿ) time and O(n) space. solve(day, last) = the best over activities a != last of points[day][a] + solve(day - 1, a).

Which edge cases should I test for Geek's Training?

A single day (take the max).