Minimum Cost For Tickets - Leetcode Solution

Description:

You have to travel to N cities from city 1 to N. There are different costs for ticket purchases. You have to minimize the sum of the ticket costs to reach the destination.

Limited passes:

1-day ticket - costs 1 unit. 7-day ticket - costs 7 units. 30-day ticket - costs 30 units.

Note: The above prices are not interrelated. Each ticket is bought for the exact number of days. In that way, if you want to fly from day i to day j (j > i), you have to buy passes covering all the days between i and j.

Example:

Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11 Explanation: The week pass is valid for days 1, 2, 3, 4, 5, 6, and 7. The day pass is valid for everyday. The month pass is valid for days 1 to 30 of every month. The total price using this strategy is: 2 + 7 + 2 = 11.

Solution:

To address this issue, we can utilize dynamic programming. Before we begin programming, let's think about the recursive formula for the issue.

dp[i] represents the minimum expense expected to fly from city 1 to city i. Then, we can reinforce the recursive formula.

case 1. When we don't require a travel pass

If we don't need a travel pass for city i, the recursive formula dp[i] = dp[i - 1]

case 2. When we need to purchase a travel pass

If we need to purchase a travel pass for city i, there can be three forms of passes: the 1-day pass, the 7-day pass, and the 30-day pass. The issue requires us to locate the minimum of the three.

dp[i] = min(dp[i - 1] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2])

Here, we set the max() limit so that we don't transcend the range when we buy the pass earlier in the array than city i. The costs[] categories store the price of the day pass, week pass, and month pass, sequentially.

In summary, we have two scenarios. If we don't require a travel pass for city i, take the previous optimal cost. If we need the pass, pick between the present cost and the pass cost plus the minimum optimized expense at 7 or 30 days before the present day.

We can extend the above formula to the whole array, resulting in O(N) possible answers. Fortunately, due to many overlapping sub-problems, we can use dynamic programming to save time.

1