是否计划查找使用Python整天旅行的最低巴士票价？

假设我们有一个称为天的排序数字列表，我们每天必须在那儿坐公共汽车。我们必须找到全天旅行所需的最低费用。巴士票有3种类型。1天通行证2块钱7天通行证7块钱30天通行证25块钱

因此，如果输入像days = [1、3、5、6、28]，则输出将为9，因为可以通过在开始时购买7天通行证然后再购买1天来获得最低成本第29天的一日通行证。

为了解决这个问题，我们将按照以下步骤操作：

• n：=天数上限

• 天：=天的新集合

• dp：= [0] *（n + 1）

• 对于介于1到n + 1的i

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

• 如果我> = 30，则

• 否则，当我> = 7时，

• 除此以外，

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

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

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

• 如果我的天数不为零，则

• 除此以外，

• 返回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