Minimum Cost Ticket
Application of Dynamic Programming: Compute Optimal Path To Target Approach

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

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 1day pass is sold for costs[0] dollars;
a 7day pass is sold for costs[1] dollars;
a 30day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel. For example, if we get a 7day 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 1day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1day 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 30day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1day 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 1day, 7days or 30days 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 1day pass, dp[i  7] + cost of a 7day pass, dp[i  30] + cost of a 30day 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 wellcommented code demonstrates how to achieve our goal using everything discussed above.
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.