用 Python 编写程序来查找所有日子的最低公交车票价?

pythonserver side programmingprogramming更新于 2026/2/16 6:04:17

假设我们有一个排序数字列表，称为天数，我们必须每天乘坐公交车。我们必须找到所有日子旅行所需的最低费用。有 3 种类型的公交车票。 1 天通票 2 美元 7 天通票 7 美元 30 天通票 25 美元

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

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

n := 最大天数
days := 来自 days 的新集合
dp := [0] *(n + 1)
对于范围为 1 到 n + 1 的 i，执行
- 如果 days 中的 i 非零，然后
  - 如果 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))