Python程序：查找所有出行日期的最低公交票价？

假设我们有一个称为days的已排序数字列表，其中包含我们必须在每一天乘坐公交车的日期。我们必须找到乘坐所有日期的最低成本。有三种类型的公交票。1日票价为2美元，7日票价为7美元，30日票价为25美元。

因此，如果输入类似于 days = [1, 3, 5, 6, 28]，则输出将为 9，因为最低成本可以通过在开始时购买 7 日票，然后在第 29 天购买 1 日票来实现。

为了解决这个问题，我们将遵循以下步骤

  • n := days中的最大值

  • days := 从days创建的新集合

  • dp := [0] *(n + 1)

  • 对于 i 从 1 到 n + 1，执行以下操作

    • 如果 i 在 days 中存在，则

      • 如果 i >= 30，则

        • dp[i] := dp[i - 1] + 2，dp[i - 7] + 7，dp[i - 30] + 25 的最小值

      • 否则，如果 i >= 7，则

        • dp[i] := dp[i - 1] + 2，dp[i - 7] + 7，25 的最小值

      • 否则，

        • dp[i] := dp[i - 1] + 2，7 的最小值

    • 否则，

      • dp[i] := dp[i - 1]

  • 返回 dp[n]

让我们看看以下实现以获得更好的理解

示例

 实时演示

class Solution:
   def solve(self, days):

      n = max(days)
      days = set(days)

      dp = [0] * (n + 1)

      for i in range(1, n + 1):
         if i in days:
            if i >= 30:
               dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25)
            elif i >= 7:
               dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, 25)
            else:
               dp[i] = min(dp[i - 1] + 2, 7)
         else:
            dp[i] = dp[i - 1]

      return dp[n]

ob = Solution()
days = [1, 3, 5, 6, 28]
print(ob.solve(days))

输入

[1, 3, 5, 6, 28]

输出

9

更新于: 2020年11月10日

828 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告