---
# System prepended metadata

title: 983. Minimum Cost For Tickets
tags: [Leetcode, Python]

---

# 983. Minimum Cost For Tickets
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/minimum-cost-for-tickets/description/

## MyCode!
```python=
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0]* 366
        for i in days:
            dp[i] = 1 # i 用來表示第 i 天所需要的旅遊花費
        for i in range(1,366):
            if dp[i] == 0: # 這狀況表示沒有出去玩
                dp[i] = dp[i-1] # 前一天的花費等於今天的花費
            else: # 有出去玩的狀況
                dp[i] = min(costs[0] + dp[i-1], costs[1] + dp[max(0,i-7)], costs[2] + dp[max(0,i-30)])
        return dp[-1]
            
```

## 解題思路 ＆ 步驟
* 題目會給出一年之中要旅行的日子（days）跟花費（costs），可以使用動態規劃 DP 紀錄最小花費（~~*但其實我不太會 DP 這樣說很裝Ｂ*~~）
### Step 1：做出一個空的 List ，裡面裝 366 個 0
* 因為一年有 365 天

![](https://i.imgur.com/X40L4Pd.png)

### Step 2：利用題目給的**旅行日（days）** 當作 index， List[days] 的值改為 1 。讓全 0 的 List 中留下要旅行的記號 1
![](https://i.imgur.com/5iBISWo.png)
### Step 3：標記好後，會由全年的第 1 天記錄到第 365 天，看每天累計的最小花費是多少

![](https://i.imgur.com/4mXKRsX.png)

* 如果跑到第 i 天，他的值是 0 ，代表沒有出去玩，前一天的花費就會等於今天的花費

* 其他狀況屬於有出去玩，把第 i 天的值更新為所有日子最小花費
     1. **一天券的錢 ＋ 前面累積花費：**`costs[0] + dp[i-1]` ，表示我今天要買一天券用
     2. **七天券的錢 ＋ 七天前累積花費：**`costs[1] + dp[max(0,i-7)]`，表示從七天前到今天我要用七天券
     3. **三十天券的錢 ＋ 三十天前累積花費：**`costs[2] + dp[max(0,i-30)])`，表示從三十天前到今天我要用三十天券

### Step 4 : Return List[-1]（最後累積的最小花費）
