## 题目

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`

.

**Example 1:**

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

**Example 2:**

1 | Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] |

**Note:**

`1 <= days.length <= 365`

`1 <= days[i] <= 365`

`days`

is in strictly increasing order.`costs.length == 3`

`1 <= costs[i] <= 1000`

## 思路

DP.

1 | dp[i]表示旅行到i天为止需要的最少旅行价格。 |

则递推公式为：

`dp[i] = dp[i - 1]`

当第i天不用旅行`dp[i] = min(dp[i - 1] + costs[0], dp[i - 7] + costs[1], dp[i - 30] + costs[2])`

当第i天需要旅行

注意一下向前查找的时候是否越界。

## 代码

1 | class Solution: |