The blog for Design Patterns, Linux, HA and Myself!

24
May 2020

This document presents the solution to the problem Minimum Cost For Tickets - Leetcode.

Note: Make sure to go through the code comments as well. It’ll help you understand the concept better.

` ````
In a country popular for train travel, you have planned some train travelling 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.
```

I’ll first try solving it by a brute force approach then I’ll move to a more optimal solution. While approaching towards the optimal solution, I’ll provide the approach behind the optimal solution.

Let’s start with the very first input:

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

The `days`

variable contains the exact 6 days on which a user can travel and, the `cost`

variable contains the cost of
1 day, 7 day and 30 day tickets respectively.

`cost[0]`

means the amount that the user has to pay for buying a one day’s ticket.`cost[1]`

means the amount that the user has to pay for buying a 7 days’ ticket. If the user has bought this ticket on 2nd day then they can travel on 2nd, 3rd, 4th, 5th, 6th, 7th and the 8th day using the same ticket.`cost[2]`

means the amount that the user has to pay for buying a 30 days’ ticket. Just like`cost[1]`

but for 30 days.

Now, let’s proceed to solve it in a brute force way.

One the 1st day, the user can buy the 1day ticket, and it will be valid for that day only, or the user can buy the 7day ticket that will remain valid until 7th, or they can buy the 30day ticket thus making themselves able to travel on all days because the ticket will remain valid until 20th.

So, which ticket the user should buy?

They can buy 1day ticket on all the days, making the total cost = 12(6 * 2).

They can also buy one 7day ticket on 1st and then one 1day ticket on 8th and 20th, which makes the total cost = 11(7 + 2+ 2)

Or, they can buy the 30day ticket on 1st which will remain valid for all the days in this array. Here cost = 15

You might have observed that they are multiple choices the user can make on each of the day, however, they have to make sure the total amount spent remains minimum. For this example, the best solution is to buy one 7day ticket and two 1day tickets on 8 and 11.

What I’ll do in the brute force approach is to allow the user to buy all the types of tickets whenever they can and keep a cost of tickets. Once they reach the last day of the travel, I’ll compare their cost with the minimum cost. The minimum cost will be updated with current cost if that is lower.

For the input:

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

This our flow diagram:

In this diagram, you can see that on the first day the user had the choice to buy all the tickets so all the three tickets were bought and then based on the choices available they move ahead and finally travel the last day.

On the last day, the costs from all the choices are available, and the decision can be made to select the last one.

This is the code that I’ve written for brute force:

```
// mincostTickerBruteForce is called to get the solution.
func mincostTickerBruteForce(days []int, costs []int) int {
return mincostNextDay(0, 0, 0, days, costs)
}
// mincostNextDay is called by mincostTickerBruteForce and then it calls itself recursively.
// Each successive recursion is the for proceeding to the next day after one of the ticket
// is bought.
func mincostNextDay(currentDayIndex, validTill, totalCost int, days, cost []int) int {
currentDay := days[currentDayIndex]
if currentDayIndex == len(days)-1 {
// this block is executed if the current day is the last day
if currentDay <= validTill {
// the final cost will be the totalCost if the ticket for
// the current day was bought earlier
return totalCost
} else {
// this block is executed if the user needs to buy the ticket
// for the last day
// here we pick the smallest between
// cost[0], cost[1] and cost[2]
// and add it to the totalCost
nextCostToPick := 0
if cost[0] <= cost[1] && cost[0] <= cost[2] {
nextCostToPick = cost[0]
} else if cost[1] <= cost[0] && cost[1] <= cost[2] {
nextCostToPick = cost[1]
} else {
nextCostToPick = cost[2]
}
return totalCost + nextCostToPick
}
}
minCost := math.MaxInt32
if currentDay <= validTill {
// this if block is executed if there is no need to buy a ticket for current day
// as it was already purchased earlier using a 7day or a 30day ticket.
minCost = mincostNextDay(currentDayIndex+1, validTill, totalCost, days, cost)
} else {
// this block is executed if the user has to buy the ticket for the current day
// in this section user buys the ticket for the current day
newCost := totalCost + cost[0]
// the ticket is valid till current day as the ticket is bought only for the
// current day
newValidTill := currentDay
// proceed to the next day
minCost = mincostNextDay(currentDayIndex+1, newValidTill, newCost, days, cost)
// in this section user buys the ticket for the next 7 days
newCost = totalCost + cost[1]
// as the ticket is a 7day ticket, it remains valid for the next 6 days
newValidTill = currentDay + 6
thisCost := mincostNextDay(currentDayIndex+1, newValidTill, newCost, days, cost)
if thisCost < minCost {
minCost = thisCost
}
// here the 30day ticket is bought
newCost = totalCost + cost[2]
newValidTill = currentDay + 29
thisCost = mincostNextDay(currentDayIndex+1, newValidTill, newCost, days, cost)
if thisCost < minCost {
minCost = thisCost
}
}
return minCost
}
```

That was out brute force approach. If you find that I can be improved further then please provide your feedback in the comment section below.

We can, definitely, work on an optimal solution here because there will be `Stackoverflow`

error if the input size is
big.

Let’s proceed to solve this question in new way using the brute force approach that we’ve just created.

We’ll be using this matrix to solve our question from now on:

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | ||||||

7 | ||||||

15 | ||||||

Min Cost |

The first row contains all the days on which the user has to travel, and the first column cost for 1day, 7day and 30day. The last row will contain the minimum cost for travelling on the nth day.

So, let’s buy the tickets for the 1st day:

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | 2 | |||||

7 | 7 | 7 | 7 | 7 | ||

15 | 15 | 15 | 15 | 15 | 15 | 15 |

Min Cost | 2 | 7 | 7 | 7 | 15 | 15 |

- If the user buys the 1day ticket on 1st day then he can travel on the first day.
- If they buy the 7day ticket then they can travel on 1st, 4th, 6th and 7th day in 7 dollars.
- If they buy the 30day ticket then they can travel on 1st, 4th, 6th, 7th, 8th and 20th day in 15 dollars.

In the last row I’ve added the minimum cost for travelling for each of the days.

Now, let’s buy the tickets for the 4th day:

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | 2 | 4 | ||||

7 | 7 | 7 | 7 | 7 | 9 | |

15 | 15 | 15 | 15 | 15 | 15 | 15 |

Min Cost | 2 | 4 | 7 | 7 | 9 | 15 |

The total cost until 1st day has been 2 dollars. Now,

- If the user buys the 1day ticket on 4th day then he can travel that day. The total cost will be 4(2 + 2) dollars.
- If they buy the 7day ticket then they can travel on 4th, 6th, 7th and 8th day in 9(2 + 7) dollars. But, apart from the 8th day, the user can travel on all the other days in 7 dollars. So, I’ll just update the cost of 8th day.
- If they buy the 30day ticket then they can travel on 4th, 6th, 7th, 8th and 20th day in 17(2 + 15) dollars. But it is of no use as the user can travel on all the days with a lesser cost.

The minimum cost for travelling on the 4th day is 4 dollars.

Now, let’s buy the tickets for the 6th day:

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | 2 | 4 | 6 | |||

7 | 7 | 7 | 7 | 7 | 9 | |

15 | 15 | 15 | 15 | 15 | 15 | 15 |

Min Cost | 2 | 4 | 6 | 7 | 9 | 15 |

- If the user buys the 1day ticket on 6th day then he can travel that day. The total cost will be 6(2 + 4) dollars.
- If they buy the 7day ticket then they can travel on 6th, 7th and 8th day in 11(7 + 4) dollars but it is greater than the cost of travelling on those days.
- There is no point in buying the 30day ticker here because the user can travel on all the days with a lesser value

The minimum cost for travelling on the 6th day is 6 dollars.

Now, the tickets for the 7th day:

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | 2 | 4 | 6 | 8 | ||

7 | 7 | 7 | 7 | 7 | 9 | |

15 | 15 | 15 | 15 | 15 | 15 | 15 |

Min Cost | 2 | 4 | 7 | 7 | 9 | 15 |

The user can buy a 1day ticket on the 8th day and then the cost will be 8(2 + 6) dollars, but they can already travel on the 8th day with 7 dollars.

Now, the tickets for the 8th day:

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | 2 | 4 | 6 | 8 | 9 | |

7 | 7 | 7 | 7 | 7 | 9 | |

15 | 15 | 15 | 15 | 15 | 15 | 15 |

Min Cost | 2 | 4 | 7 | 7 | 9 | 15 |

Finally, for the 20th day

days/cost | 1 | 4 | 6 | 7 | 8 | 20 |
---|---|---|---|---|---|---|

2 | 2 | 4 | 6 | 8 | 9 | 11 |

7 | 7 | 7 | 7 | 7 | 9 | |

15 | 15 | 15 | 15 | 15 | 15 | 15 |

Min Cost | 2 | 4 | 7 | 7 | 9 | 15 |

- The user can buy a 1day ticket and the cost will be 11(2 + 9) dollars and it is less than the previous cost, 15 dollars. So, the minimum cost to travel on the 20th day is 11.

This is how we’ll be solving this problem, by solving it for each of the days, i.e., Dynamic Programming.

I’m adding the code for the solution here. What I’ll do is:

- Create an array,
`minTicketCost`

, for keeping the minimum cost of for each of the days. It is the last row of our table. - The variable,
`prevDayMinCost`

, will store the minimum cost to travel on the previous day. This is cost that we’ve been adding to our current day’s cost. - And, then I’m looping over each of the day in the array and find the minimum cost for that day. If the 7day or the
30day ticker is bought then I’m updating the array
`minTicketCost`

for the future days as well.

```
func mincostTickets(days []int, costs []int) int {
minTicketCost := make([]int, len(days))
for i := range minTicketCost {
// initialize all the elements with max int32 so that it will always be greater
// than the values that we'll encounter
minTicketCost[i] = math.MaxInt32
}
prevDayMinCost := 0
for i := 0; i < len(days); i++ {
// buy 1day ticket
nextCost1 := prevDayMinCost + costs[0]
// buy 7day ticket
nextCost7 := prevDayMinCost + costs[1]
// update the cost for next 7 days
for j := i + 1; j < len(days); j++ {
if days[j] > days[i]+6 {
break
}
if minTicketCost[j] > nextCost7 {
minTicketCost[j] = nextCost7
}
}
// buy 7day ticket
nextCost30 := prevDayMinCost + costs[2]
// update the cost for next 30 days
for j := i + 1; j < len(days); j++ {
if days[j] > days[i]+29 {
break
}
if minTicketCost[j] > nextCost30 {
minTicketCost[j] = nextCost30
}
}
// the min cost is found here for the current day
if nextCost1 <= nextCost7 && nextCost1 <= nextCost30 {
prevDayMinCost = nextCost1
} else if nextCost7 <= nextCost1 && nextCost7 <= nextCost30 {
prevDayMinCost = nextCost7
} else {
prevDayMinCost = nextCost30
}
// if the min cost is lower then we update the array, minTicketCost
if prevDayMinCost < minTicketCost[i] {
minTicketCost[i] = prevDayMinCost
} else {
prevDayMinCost = minTicketCost[i]
}
fmt.Println(minTicketCost)
}
return prevDayMinCost
}
```

Loading Comments...