Travel Pass Planner

Medium1-D Dynamic Programming

Problem

You commute on the days listed in days (strictly increasing, between 1 and 365). The transit company sells three passes, with prices in costs: costs[0] for a 1-day pass, costs[1] for a 7-day pass and costs[2] for a 30-day pass.

A pass bought on day d covers days d through d + length - 1. Return the minimum total cost to cover every commuting day.

Example 1

Input:
days = [1, 4, 6, 7, 8, 20], costs = [2, 7, 15]
Output:
11

1-day pass on day 1 (2), 7-day pass on day 4 covering 4–10 (7), 1-day pass on day 20 (2).

Example 2

Input:
days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], costs = [2, 7, 15]
Output:
17

30-day pass on day 1 (15) plus a 1-day pass on day 31 (2).

Constraints

  • 1 ≤ days.length ≤ 365
  • 1 ≤ days[i] ≤ 365, strictly increasing
  • costs.length = 3
  • 1 ≤ costs[i] ≤ 1000

Hint

Show the first hint

Walk the calendar day by day. What is the cheapest way to have everything up to day d covered?

Walkthrough

How to approach it

01Clarify before coding

  • Can passes overlap? Yes, though it is never needed.
  • Is a longer pass ever cheaper than a shorter one? Possibly; the DP handles any prices.
  • Do I need to cover days after the last travel day? No.

02Brute force

At each uncovered travel day try all three passes and recurse to the first travel day not covered. Memoising on that index gives an O(n) DP over travel days.

Cost: Without memo: O(3ⁿ). With memo: O(n) states, each scanning forward to the next uncovered day.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.