用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用

Jacques Bopp on Unsplash

題目敘述 Minimum Cost For Tickets

題目會給定兩個陣列。
第一個是日期陣列days，代表外出旅遊的是哪幾天。
第二個是成本陣列costs，代表火車一日票、七日票、30日的月票的票價。

請問火車旅行支出的最小費用是多少？

測試範例

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

在第一天買一日票，可以覆蓋第一天。
在第三天​買七日票，可以覆蓋第三天~第九天，
在第20天買一日票，可以覆蓋第20天​

最小支出為 一日票 + 七日票 + 一日票 ​= 2元 + 7元 + 2元 = 11元

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

在第一天買30日票，可以覆蓋第一天~第三十天。
在第三十一天​買一日票，可以覆蓋第三​十一天，

最小支出為 30日票 + 一日票 ​= 15​元 + 2元 = 17元

約束條件

Constraints:

• 1 <= days.length <= 365

旅行日陣列長度介於1~365

• 1 <= days[i] <= 365

每個旅行日一定是一年內的某一天。

• days is in strictly increasing order.

旅行日嚴格遞增分布。

• costs.length == 3

火車票價陣列長度為三，分別對應 一日票、七日票、30日票的價格。

• 1 <= costs[i] <= 1000

車票價格介於1元~1000元之間。

觀察 所有選擇，挑一個費用最小的方案。

第一直覺可能會這樣想，那就都一口氣買30日的月票就好啦！

不過，一口氣買30日的月票並不是最佳解，因為並不是每天都是出遊日。
根據出遊的情況，做出能夠覆蓋旅遊日期，同時兼顧支出費用最小才是正確的。

假如我們今天要出遊，有那些選擇?

其實就是三種選擇，

第一種是買一日票，只能覆蓋今天。

第二種是買七日票，可以覆蓋最靠近的連續七天。

第三種是買30日票(月票)，可以覆蓋最靠近的連續三十天。

我們要做的就是從這三種選擇裡面，
挑一個能夠盡量覆蓋出遊日期，又兼顧支出費用最小的選擇。

示意圖

演算法 DP動態規劃 + 可選擇的車票方案

1.定義DP狀態

承接觀察點的思考，定義DP[ day ] 代表從第一天 到 day這天的累積最小支出費用。

最後所求是什麼?

就是全部旅行日的最小支出，DP[ days[-1] ]

也就是從第一天到最後一個旅行日的總支出最小費用。

2.推導DP狀態轉移關係式

假如我們今天要出遊，有那些選擇?

其實就是三種選擇，

第一種是買一日票，只能覆蓋今天。

第二種是買七日票，可以覆蓋最靠近的連續七天。

第三種是買30日票(月票)，可以覆蓋最靠近的連續三十天。

我們要做的就是從這三種選擇裡面，

挑一個能夠盡量覆蓋出遊日期，又兼顧支出費用最小的選擇。

DP[ day ]
= min( 一日票 + DP[ day-1], 七日票 + DP[day-7], 30日票 + DP[ day-30] )

假如我們今天沒有出遊呢?

那也很簡單，沒有出遊，自然沒有支出費用，直接回溯檢查前一天day-1即可。

DP[ day ] = DP[ day - 1 ]

3.釐清DP初始狀態

最小規模的問題是什麼?

就是當回溯到旅行出發之前的時候，都還沒開始旅行，肯定沒有費用，支出=0

DP[ day ] = 0

程式碼 DP動態規劃 + 可選擇的車票方案

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        
        # To speed-up travel day look-up, so make it a hashSet.
        travel_days = set(days)

        ## DP table
        # index: day
        # value: minimal cost up to day so far
        dp = {}

        def travel(day):
            
            # Look-up DP table
            if day in dp:
                return dp[day]
            
            ## Base case
            # Before day_0, no traverl anymore, therefore no cost
            if day <= 0:
                return 0

            ## General cases:
            
            # Not in travel day, just backtrack to previous day directly
            elif day not in travel_days:
                dp[day] = travel(day-1)
                return dp[day]

            # Today is travel day, pick the one which is of minimal cost
            one_pass = travel(day-1) + costs[0]
            seven_pass = travel(day-7) + costs[1]
            monthly_pass = travel(day-30) + costs[2]

            dp[day] = min( one_pass, seven_pass, monthly_pass)
            return dp[day]
            
        #-----------------------------------------------
        return travel( day = days[-1] )

複雜度分析

令days陣列的長度為n

時間複雜度:O(n)

線性掃描每個旅行日，每個旅行日可以在O(1)內挑出最好的車票方案，總共耗時O(n)

空間複雜度:O(n)

DP table 和 travel_days集合 所需空間皆為O(n)

關鍵知識點 所有選擇，挑一個費用最小的方案。

假如我們今天要出遊，有那些選擇?

其實就是三種選擇，

第一種是買一日票，只能覆蓋今天。

第二種是買七日票，可以覆蓋最靠近的連續七天。

第三種是買30日票(月票)，可以覆蓋最靠近的連續三十天。

我們要做的就是從這三種選擇裡面，

挑一個能夠盡量覆蓋出遊日期，又兼顧支出費用最小的選擇。

Reference

[1] Minimum Cost For Tickets - LeetCode

回到DP特訓班目錄 和 學習路徑