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.