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

Arnab Chakraborty

更新於: 2020年11月10日

828 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習