主題
題目連結(jié)：
題目意譯：
你提前一年計畫著一些搭火車的行程。在接下來的一年內(nèi)會搭火車的天數(shù)以一個整數(shù)陣列 days 給定。每一天是以一個介於 1（含）到 365（含）之間的整數(shù)所表示。
火車票有三種售票方式：
一個「一日通行證」售價為 costs[0] 元、
一個「七日通行證」售價為 costs[1] 元、
一個「三十日通行證」售價為 costs[2] 元。
這些通行證根據(jù)其名字可以允許對應(yīng)天數(shù)的火車自由通行。
例如說，如果我們在第 2 天買一個七日通行證，則我們可以搭 7 天的火車：即第 2 、 3 、 4 、 5 、 6 、 7 和 8 天。
回傳你最少所需的金錢量，使得你可以在給定的 days 中每一天都有火車可以搭。
限制：
1 ≦ days.length ≦ 365
1 ≦ days[i] ≦ 365
days 嚴格遞增。
costs.length == 3
1 ≦ costs[i] ≦ 1000
範例測資：
範例 1：
輸入： days = [1,4,6,7,8,20], costs = [2,7,15]
輸出： 11
解釋： 例如，以下為一個可以讓你執(zhí)行你的火車行的通行證購買方式：
在第 1 天，你用 costs[0] = 2 元買一張一日通行證，其可以應(yīng)付第 1 天。
在第 3 天，你用 costs[1] = 7 元買一張一日通行證，其可以應(yīng)付第 3 、 4 、 …… 、 9 天。
在第 20 天，你用 costs[0] = 2 元買一張一日通行證，其可以應(yīng)付第 20 天。
你總計花費了 11 元來應(yīng)付每一天需要搭車的日程。
範例 2：
輸入： days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
輸出： 17
解釋： 例如，以下為一個可以讓你執(zhí)行你的火車行的通行證購買方式：
在第 1 天，你用 costs[2] = 15 元買一張一日通行證，其可以應(yīng)付第 1 、 2 、 …… 、 30 天。
在第 31 天，你用 costs[0] = 2 元買一張一日通行證，其可以應(yīng)付第 20 天。
你總計花費了 17 元來應(yīng)付每一天需要搭車的日程。
解題思維：
定義一個陣列 D，其中 D[i] 代表著只應(yīng)付第 1 ～ i 天中需要搭車的那幾天的話最少所需的金額。
可以看到其遞迴式為：
對於 i ≦ 0，D[i] = 0；
對於 i > 0，D[i] = min(D[i - 1] + costs[0], D[i - 7] + costs[1], D[i - 30] + costs[2])。
最後所求即為 D[365]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
