# Dynamic Programming

## 983. Minimum Cost For Tickets

You are given a list of days which you are traveling on. To travel you are required to buy a ticket for each day, there are three types of ticket passes with different costs that you can buy, each pass covers your travel for a consecutive number of days:

- 1-day pass(
`costs[0]`

) - 7-day pass(
`costs[1]`

) - 30-day pass(
`costs[2]`

)

The goal is the find the minimum cost to be able to travel on all the given days.

**Example:**

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

Output: 11

You buy a 1-day pass for day 1, a 7-day pass(covering day 4 through day 10) for days 4,6,7,8 and a 1-day pass for day 20.

**Solution:**

**Approach:** *DP with memoization*. Define an array `dp`

where `dp[i]`

represents the minimum cost to travel each day
in the given list of days AND not later than day `i`

.
For example, in the above example, `dp[4]`

and `dp[5]`

are both the minimum cost required to travel on `days=[1,4]`

.
The final answer is equal to `dp[365]`

or `dp[max(days)]`

.