Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

Topic describes

In a country where train travel is popular, you plan some train trips a year in advance. In the following year, the days you will travel will be given as an array named days. Each term is an integer from 1 to 365.

Train tickets are sold in three different ways:

  • A one-day pass costs $[0].
  • A seven-day pass costs $[1].
  • A 30-day pass costs us $[2].

The pass allows unlimited travel for several days. For example, if we get a seven-day pass on day 2, we can travel for seven days in a row: day 2, Day 3, day 4, day 5, day 6, day 7, and day 8.

Returns the minimum amount of money you want to spend to complete each of the trips listed in the given list days.

Example 1: input: days = [1,4,6,7,8,20], costs = [2,7,15] output: 11 explanation: for example, here is a way to buy a pass that allows you to complete your travel plans: On day 1, you pay costs[0] = 2 for a one-day pass that will take effect on day 1. On the third day, you pay costs[1] = 7 for a 7-day pass that will be available on the 3rd, 4th… Effective in 9 days. On the 20th day, you pay costs[0] = 2 for a one-day pass that will take effect on the 20th day. You spent a total of 11 and completed every day of your planned trip.

Example 2: input: days =,2,3,4,5,6,7,8,9,10,30,31 [1], costs =,7,15 [2] output: 17 explanation: for example, there is a way to buy pass, can let you finish your travel plan: On the first day, you buy a 30-day pass that costs[2] = 15. Effective in 30 days. On day 31, you pay costs[0] = 2 for a one-day pass that will take effect on day 31. You spent a total of 17 and completed every day of your planned trip.

Thought analysis

Dynamic programming, we still follow the steps of dynamic programming to solve the problem.

Define state

Define a one-dimensional data dp, dp[I] represents the minimum cost from day 1 to day I, so we need to solve dp[365], remember the lastDay in days as lastDay, since there is no cost after lastDay, so we actually solve dp[lastDay].

State transition equation

This can be divided into 2 cases:

  • I is not one of the days, so obviously you don’t need to spend for the I day, so there is
dp[i] = dp[i-1]
Copy the code
  • I is one of the days. To satisfy the definition of DP, dp[I] represents the period from day 1 to day I, so we definitely don’t want this ticket to be valid after day I. There are three median tickets in total, and I is the last day of these three kinds of tickets
dp[i] = min(dp[i-1]+costs[0], dp[i-7]+costs[1], dp[i-30]+costs[2])
Copy the code

The boundary conditions

Remember the firstDay as “firstDay”, then the cost of any day before “firstDay” is 0. In particular, we can see the above state transition equation, dp[i-1], DP [i-7], dp[i-30] may be non-existent days, and the cost can also be considered as 0.

Java version code

class Solution { public int mincostTickets(int[] days, int[] costs) { int len = days.length; int lastDay = days[len-1]; int[] dp = new int[lastDay+1]; int index = 0; for (int i = 1; i <= lastDay; i++) { if (i ! = days[index]) { dp[i] = dp[i-1]; } else { dp[i] = Integer.min((i>=1? dp[i-1]:0) + costs[0], Integer.min((i>=7? dp[i-7]:0) + costs[1], (i>=30? dp[i-30]:0) + costs[2])); index++; } } return dp[lastDay]; }}Copy the code