983。最低門票費(fèi)用

難度：中等

主題：數(shù)組，動(dòng)態(tài)規(guī)劃

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

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

• 1 天通票售價(jià)為 [0] 美元，
• 7 天通票售價(jià)為 [1] 美元，并且
• 30 天通票售價(jià)為 [2] 美元。

通行證允許連續(xù)旅行很多天。

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

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

示例1：

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

示例2：

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

約束：

• 1
• 1
• 天數(shù)嚴(yán)格按遞增順序排列。
• costs.length == 3
• 1

解決方案：

該問題涉及確定一年中一組指定日期的最低旅行成本。該問題提供三種類型的旅行通行證：1 天、7 天和 30 天通行證，每種都有特定的費(fèi)用。我們的目標(biāo)是找到使用這些通行證覆蓋所有旅行日的最便宜的方式。該任務(wù)需要使用動(dòng)態(tài)規(guī)劃來有效計(jì)算最小成本。

要點(diǎn)

• 動(dòng)態(tài)規(guī)劃（DP）：我們使用動(dòng)態(tài)規(guī)劃來跟蹤每天的最低成本。
• 旅行天數(shù)：旅行天數(shù)按嚴(yán)格遞增順序提供，這意味著我們確切地知道需要旅行哪些天。
• 三種類型的通行證：對于 days 數(shù)組中的每一天 d，通過考慮購買涵蓋當(dāng)天 d 的通行證的成本來計(jì)算最低成本：
  • 1 日通行證：費(fèi)用為 1 日通行證的費(fèi)用 (costs[0]) 加上前一天的費(fèi)用 (dp[i-1])。
  • 7 天通行證：費(fèi)用為 7 天通行證的費(fèi)用（費(fèi)用[1]）加上 d 日起 7 天內(nèi)的最近一天的費(fèi)用。
  • 30 天通行證：費(fèi)用為 30 天通行證的費(fèi)用（費(fèi)用[2]）加上 d 后 30 天內(nèi)的最近一天的費(fèi)用。
• 基本案例：未完成行程的一天的最低費(fèi)用為 0。

方法

1. DP 數(shù)組：我們將使用 DP 數(shù)組 dp[]，其中 dp[i] 表示涵蓋截至 i 天的所有旅行日的最低成本。
2. 填充 DP 數(shù)組：對于從 1 到 365 的每一天：
   • 如果當(dāng)天是旅行日，我們會(huì)考慮以下因素來計(jì)算最低費(fèi)用：
     • 使用一日通票的費(fèi)用。
     • 使用 7 天通票的費(fèi)用。
     • 使用 30 天通行證的費(fèi)用。
   • 如果當(dāng)天不是出行日，當(dāng)天的費(fèi)用將與前一天相同（dp[i] = dp[i-1]）。
3. 最終答案：填滿DP數(shù)組后，最低費(fèi)用將存儲(chǔ)在dp[365]中，它涵蓋了所有可能的旅行天數(shù)。

計(jì)劃

1. 初始化一個(gè)大小為 366 的數(shù)組 dp[]（一個(gè)額外的數(shù)組可處理最多 365 天）。
2. 將 dp[0] 設(shè)置為 0，因?yàn)榈?0 天沒有成本。
3. 創(chuàng)建一組 tripDays 以快速檢查特定日期是否為旅行日。
4. 從 1 到 365 迭代每一天：
   • 如果是旅行日，請考慮每種通票類型來計(jì)算最低費(fèi)用。
   • 如果沒有，結(jié)轉(zhuǎn)前一天的費(fèi)用。
5. 返回 dp[365] 處的值。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：983。最低門票費(fèi)用

<?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
?>

解釋：

• 算法會(huì)迭代一年中的每一天（365 天）。
• 對于每個(gè)旅行日，它會(huì)通過考慮是否更便宜來計(jì)算成本：
  • 購買 1 日通行證（將 1 日通行證的費(fèi)用添加到前一天的費(fèi)用中）。
  • 購買7天通票（加上7天通票的費(fèi)用并考慮過去7天的旅行費(fèi)用）。
  • 購買30天通票（加上30天通票的費(fèi)用并考慮過去30天的旅行費(fèi)用）。
• 如非出行日，費(fèi)用與前一天相同。

示例演練

示例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.

時(shí)間復(fù)雜度

解決方案的時(shí)間復(fù)雜度為O(365)，因?yàn)槲覀兊荒曛械乃腥兆樱⑶覍τ诿恳惶?，我們?zhí)行恒定時(shí)間操作（檢查行程天數(shù)并更新 DP）大批）。因此，解決方案以相對于天數(shù)的線性時(shí)間運(yùn)行。

示例輸出

示例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

該解決方案使用動(dòng)態(tài)規(guī)劃有效計(jì)算旅行天數(shù)的最低成本。通過迭代幾天并考慮所有可能的通行證（1 天、7 天、30 天），算法找到購買通行證的最佳策略。時(shí)間復(fù)雜度與天數(shù)成線性關(guān)系，適合問題約束。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲(chǔ)庫 一個(gè)星號或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是。最低門票費(fèi)用的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！