。最低门票费用

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中文网其他相关文章！