。最低門票費用

983。最低門票費用

難度：中

主題：數組，動態規劃

您提前一年規劃了一些火車旅行。您將旅行的一年中的天數以整數數組 days 的形式給出。每天是 1 到 365 之間的整數。

火車票有三種不同的方式出售：

• 1 天通票售價為 [0] 美元，
• 7 天通票售價為 [1] 美元，且
• 30 天通票售價為 [2] 美元。

通行證允許連續旅行很多天。

• 例如，如果我們在第2天獲得7天通票，那麼我們可以旅行7天：2、3、4、5、6、7和8。

返回在給定的日期列表中每天您需要旅行的最低金額。

範例1：

• 輸入： 天 = [1,4,6,7,8,20]，成本 = [2,7,15]
• 輸出： 11
• 說明：例如，以下是購買通行證的一種方式，可讓您按照旅行計劃出行：
  • 在第 1 天，您購買了 1 天通票，費用為 [0] = 2 美元，涵蓋了第 1 天的費用。
  • 第 3 天，您購買了 7 天通行證，費用為 [1] = 7 美元，涵蓋第 3、4、...、9 天。
  • 第 20 天，您以成本 [0] = 2 美元購買了 1 日通行證，涵蓋了第 20 天。
  • 您總共花了 11 美元，涵蓋了旅行的所有天數。

範例2：

• 輸入： 天 = [1,2,3,4,5,6,7,8,9,10,30,31]，成本 = [2,7,15]
• 輸出： 17
• 說明：例如，以下是購買通行證的一種方式，可讓您按照旅行計劃出行：
  • 在第 1 天，您購買了 30 天通行證，費用 [2] = 15 美元，涵蓋第 1、2、...、30 天。
  • 在第 31 天，您購買了 1 天通行證，費用為 [0] = 2 美元，涵蓋了第 31 天。
  • 您總共花了 17 美元，涵蓋了旅行的所有天數。

約束：

• 1
• 1
• 天數嚴格依遞增順序排列。
• costs.length == 3
• 1

解：

此問題涉及確定一年中一組指定日期的最低旅行成本。該問題提供三種類型的旅行通行證：1 天、7 天和 30 天通行證，每種都有特定的費用。我們的目標是找到使用這些通行證覆蓋所有旅行日的最便宜的方式。此任務需要使用動態規劃來有效計算最小成本。

重點

• 動態規劃（DP）：我們使用動態規劃來追蹤每天的最低成本。
• 旅行天數：旅行天數是嚴格遞增順序提供，這意味著我們確切地知道需要旅行哪些天。
• 三種類型的通行證：對於 days 陣列中的每一天 d，透過考慮購買涵蓋當天 d 的通行證的成本來計算最低成本：
  • 1 日通行證：費用為 1 日通行證的費用 (costs[0]) 加上前一天的費用 (dp[i-1])。
  • 7 天通行證：費用為 7 天通行證的費用（費用[1]）加上 d 日起 7 天內的最近一天的費用。
  • 30 天通行證：費用為 30 天通行證的費用（費用[2]）加上 d 後 30 天內的最近一天的費用。
• 基本案例：未完成行程的一天的最低費用為 0。

方法

1. DP 陣列：我們將使用 DP 陣列 dp[]，其中 dp[i] 表示涵蓋截至 i 天的所有旅行日的最低成本。
2. 填滿 DP 陣列：對於 1 到 365 的每一天：
   • 如果當天是旅行日，我們會考慮以下因素來計算最低費用：
     • 使用一日通票的費用。
     • 使用 7 天通票的費用。
     • 使用 30 天通行證的費用。
   • 如果當天不是出遊日，當天的費用將與前一天相同（dp[i] = dp[i-1]）。
3. 最終答案：填滿DP數組後，最低費用將存放在dp[365]中，它涵蓋了所有可能的旅行天數。

計劃

1. 初始化一個大小為 366 的陣列 dp[]（一個額外的陣列可處理最多 365 天）。
2. 將 dp[0] 設定為 0，因為第 0 天沒有成本。
3. 建立一組 tripDays 以快速檢查特定日期是否為旅行日。
4. 從 1 到 365 迭代每一天：
   • 如果是旅行日，請考慮每種通票類型來計算最低費用。
   • 如果沒有，結轉前一天的費用。
5. 傳回 dp[365] 處的值。

讓我們用 PHP 實作這個解：983。最低票券費用

<?php /**
 * @param Integer[] $days
 * @param Integer[] $costs
 * @return Integer
 */
function mincostTickets($days, $costs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$days1 = [1, 4, 6, 7, 8, 20];
$costs1 = [2, 7, 15];
echo mincostTickets($days1, $costs1); // Output: 11

$days2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs2 = [2, 7, 15];
echo mincostTickets($days2, $costs2); // Output: 17
?>

解釋：

• 演算法會迭代一年中的每一天（365 天）。
• 對於每個旅行日，它會透過考慮是否更便宜來計算成本：
  • 購買 1 日通行證（將 1 日通行證的費用加到前一天的費用中）。
  • 購買7天通票（加上7天通票的費用並考慮過去7天的旅行費用）。
  • 購買30天通票（加上30天通票的費用並考慮過去30天的旅行費用）。
• 如非出遊日，費用與前一天相同。

範例演練

範例1：

輸入：

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];

• 第 1 天：花 2 美元購買 1 日通票。
• 第 4 天：花 7 美元購買 7 天通行證（涵蓋第 4 天至第 9 天）。
• 第 20 天：以 2 美元購買另一張 1 日通行證。

總成本 = $2 $7 $2 = $11.

範例2：

輸入：

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];

• 第 1 天：花 15 美元購買 30 天通行證（涵蓋第 1 天至第 30 天）。
• 第 31 天：花 2 美元購買 1 日通票。

總成本 = $15 $2 = $17.

時間複雜度

解決方案的時間複雜度為O(365)，因為我們迭代一年中的所有日子，並且對於每一天，我們執行恆定時間操作（檢查行程天​​數並更新DP）大批）。因此，解決方案以相對於天數的線性時間運行。

範例輸出

範例1：

$days = [1, 4, 6, 7, 8, 20];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 11

範例2：

$days = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31];
$costs = [2, 7, 15];
echo mincostTickets($days, $costs); // Output: 17

此解決方案使用動態規劃有效計算旅行天數的最低成本。透過迭代幾天並考慮所有可能的通行證（1 天、7 天、30 天），演算法找到購買通行證的最佳策略。時間複雜度與天數成線性關係，適合問題限制。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。最低門票費用的詳細內容。更多資訊請關注PHP中文網其他相關文章！