Solution


Approach 1: Dynamic Programming (Day Variant)

Intuition and Algorithm

For each day, if you don't have to travel today, then it's strictly better to wait to buy a pass. If you have to travel today, you have up to 3 choices: you must buy either a 1-day, 7-day, or 30-day pass.

We can express those choices as a recursion and use dynamic programming. Let's say dp(i) is the cost to fulfill your travel plan from day i to the end of the plan. Then, if you have to travel today, your cost is:

Complexity Analysis

  • Time Complexity: , where is the maximum numbered day in your travel plan.

  • Space Complexity: .


Approach 2: Dynamic Programming (Window Variant)

Intuition and Algorithm

As in Approach 1, we only need to buy a travel pass on a day we intend to travel.

Now, let dp(i) be the cost to travel from day days[i] to the end of the plan. If say, j1 is the largest index such that days[j1] < days[i] + 1, j7 is the largest index such that days[j7] < days[i] + 7, and j30 is the largest index such that days[j30] < days[i] + 30, then we have:

Complexity Analysis

  • Time Complexity: , where is the number of unique days in your travel plan.

  • Space Complexity: .


Analysis written by: @awice.