Ninja's training
MediumState includes yesterday's activity
Problem
Each day pick one of 3 activities for points, but not the same as the previous day. Maximize total points over n days.
Each day pick the best activity that differs from yesterday's, carrying the running best per choice.
The idea
The points available today depend on what was done yesterday, so the state is (day, last activity). For each day and each possible previous choice, take the best of the two activities that differ from it.
The trick
- State: day plus the activity that must be avoided.
- O(n × 3 × 3), which is linear in the days.
- Only the previous day's row is needed, so space is O(1).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [[1,2,5],[3,1,1],[3,3,3]] Values: 1, 2, 5.
1dp[day][last] = max over act!=last of points[day][act] + dp[day-1][act]Input
- array
- [1, 2, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- points = [[1,2,5],[3,1,1],[3,3,3]]
- Output:
- 11
- Explanation:
- Pick a different activity each day for max 11.
Example 2
- Input:
- points = [[10,40,70],[20,50,80],[30,60,90]]
- Output:
- 210
- Explanation:
- Best total is 210.
Example 3
- Input:
- points = [[1,1,1]]
- Output:
- 1
- Explanation:
- One day → best single activity 1.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.