The Cheapest Set of Travel Passes
You must travel on certain days of a year, given in increasing order. Passes come in three kinds, each valid for CONSECUTIVE days starting the day you buy it:
a 1-day pass costs c1
a 7-day pass costs c7
a 30-day pass costs c30
Print the least total cost that covers every travel day.
A pass may cover days you do not travel, and that is exactly what makes greedy rules fail. Buying the cheapest per-day rate is wrong when travel days cluster; buying a long pass at every cluster is wrong when the clusters are far apart.
Define dp[d] as the least cost to cover every travel day up to and including
day d. Then:
if d is not a travel day: dp[d] = dp[d-1] nothing new to cover
otherwise: dp[d] = min of
dp[d-1] + c1
dp[d-7] + c7
dp[d-30] + c30
Each option says "buy a pass that ENDS today", so it covers the window back to where the previous cost was already paid.
Clamp the lookbacks at 0 rather than skipping them. A 30-day pass bought on day
3 is legal and sometimes optimal, and dp[-27] must read as dp[0] = 0, not as
an error or a skipped option.