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

Customer Support: admin@thealgorists.com

Feedback Form:
https://www.thealgorists.com/Feedback.

Manage Subscriptions:
https://www.thealgorists.com/CustomerPortal
(Make sure you are logged into https://www.thealgorists.com.)
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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn