Minimum Cost Ticket

🙏
জয় শ্রী রাম
🕉

Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io

Problem Statement:

In a country popular for train travel, you have planned some train traveling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.
Train tickets are sold in 3 different ways:
a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.
Return the minimum number of dollars you need to travel every day in the given list of days.

Example 1:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.

Solution:

This problem is a direct application of Optimal Path(s) to Target approach of Dynamic Programming. In general each travel day could be reached in three different ways: by buying any of 1-day, 7-days or 30-days pass.

Optimal Substructure: From above discussion we see that, to compute result for day i we would be reusing the already computed result for day (i - 1), day (i - 7) and day (i - 30).
```
dp[i] = min(dp[i - 1] + cost of an 1-day pass,
            dp[i - 7] + cost of a 7-day pass,
            dp[i - 30] + cost of a 30-day pass)
```
Overlapping Subproblems: An already computed result for day i would be reused to compute result for day (i + 1), day (i + 7) and day (i + 30). So result for day i is getting reused not just once but multiple times due to overlapping subproblems property of this problem.

The below well-commented code demonstrates how to achieve our goal using everything discussed above.

Java Code:

Python Code:

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile

If you have any feedback, please use this form: https://thealgorists.com/Feedback.