我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 983. 最低票價 題目 在一個火車旅行很受歡迎的國度，你提前 ...
我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 983. 最低票價
題目
在一個火車旅行很受歡迎的國度，你提前一年計划了一些火車旅行。在接下來的一年裡，你要旅行的日子將以一個名為 days 的數組給出。每一項是一個從 1 到 365 的整數。
火車票有三種不同的銷售方式：
- 一張為期一天的通行證售價為 costs[0] 美元；
- 一張為期七天的通行證售價為 costs[1] 美元；
- 一張為期三十天的通行證售價為 costs[2] 美元。
通行證允許數天無限制的旅行。 例如，如果我們在第 2 天獲得一張為期 7 天的通行證，那麼我們可以連著旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在給定的列表 days 中列出的每一天的旅行所需要的最低消費。
示例 1：
輸入：days = [1,4,6,7,8,20], costs = [2,7,15]
輸出：11
解釋：
例如，這裡有一種購買通行證的方法，可以讓你完成你的旅行計劃：
在第 1 天，你花了 costs[0] = $2 買了一張為期 1 天的通行證，它將在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 買了一張為期 7 天的通行證，它將在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 買了一張為期 1 天的通行證，它將在第 20 天生效。
你總共花了 $11，並完成了你計劃的每一天旅行。
示例 2：
輸入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
輸出：17
解釋：
例如，這裡有一種購買通行證的方法，可以讓你完成你的旅行計劃：
在第 1 天，你花了 costs[2] = $15 買了一張為期 30 天的通行證，它將在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 買了一張為期 1 天的通行證，它將在第 31 天生效。
你總共花了 $17，並完成了你計劃的每一天旅行。
提示：
- 1 <= days.length <= 365
- 1 <= days[i] <= 365
- days 按順序嚴格遞增
- costs.length == 3
- 1 <= costs[i] <= 1000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-cost-for-tickets
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
解題思路
dp動態規劃
思路1-動態規劃
思路解析：動態規劃的關鍵是找到轉移方程，本題即對天票、周票、月票的動態規劃，用dp[i]表示截至到第i天旅行所需要的總花費，那麼第i天買票的邏輯為（\(i>0\)，對應實際的天數）：
- 若第i天買天票，則截至第i天總花費為\({\color{Magenta}{dp[i-1]+costs[0]}}\)，dp[0]為0，沒有第0天，天數從1開始算起；
- 若第i天買周票，則截至第i天總花費為\({\color{Magenta}{dp[i-7]+costs[1]}}\)，i小於7時，dp[i-7]用0替代；
- 若第i天買月票，則截至第i天總花費為\({\color{Magenta}{dp[i-30]+costs[2]}}\)，i小於30時，dp[i-30]用0替代；
要使得第i天花費最少，則取上面3種方案的最小值即可，對應的動態轉移方程可以表示為：
\[{\color{Magenta}{dp[i]=min(dp[i-1]+costs[0),min(dp[i-7]+costs[1),dp[i-30]+costs[2])}} \]
具體步驟：
- 初始化dp數組，dp的長度應為計劃旅行的最後一天序號+1，即dp[days[days.length-1]+1]，保證計算到最後一天；
- 將dp[days[i]]初始化為-1，表示當天要旅行需要計算花費；
- 開始動態規劃，dp[i]為0時當天未旅行，花費等於dp[i-1]，為-1時按照轉移方程計算dp[i]的花費；
- 最終dp[days[days.length-1]]即為最小總花費；
演算法複雜度: n為最後一天旅行的序號
- 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
演算法源碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月6日 下午10:48:51
* @Description: 983. 最低票價
*
*/
public class LeetCode_0983 {
}
class Solution_0983 {
/**
* @author: ZhouJie
* @date: 2020年5月6日 下午11:53:49
* @param: @param days
* @param: @param costs
* @param: @return
* @return: int
* @Description: 1-動態規劃；
*
*/
public int mincostTickets(int[] days, int[] costs) {
// 最後一天旅行的序號
int len = days[days.length - 1];
// 動態規劃dp需要len+1長度，包含最後一天
int[] allCost = new int[len + 1];
// 標記哪些天旅行了
for (int i : days) {
allCost[i] = -1;
}
int c1, c2, c3;
for (int i = 1; i < len + 1; i++) {
// 若當天未旅行，則花費等價於前一天
if (allCost[i] == 0) {
allCost[i] = allCost[i - 1];
} else {
// 買當天票的花費
c1 = allCost[i - 1] + costs[0];
// 買周票的花費：分為7天內買周票和7天外買周票
if (i >= 7) {
c2 = allCost[i - 7] + costs[1];
} else {
c2 = costs[1];
}
// 買月票的花費：分為30天內買月票和30天外買月票
if (i >= 30) {
c3 = allCost[i - 30] + costs[2];
} else {
c3 = costs[2];
}
// 截至第i天旅行的最小花費為c1、c2、c3的最小值
allCost[i] = Math.min(Math.min(c1, c2), c3);
}
}
// 最後一天即旅行總花費
return allCost[len];
}
}
