Chương trình tìm giá vé xe buýt tối thiểu để đi tất cả các ngày bằng Python?

Giả sử chúng ta có một danh sách các số được sắp xếp gọi là ngày, nơi chúng ta phải đi xe buýt vào mỗi ngày. Chúng tôi phải tìm chi phí thấp nhất để đi lại trong tất cả các ngày. Có 3 loại vé xe buýt. Vé 1 ngày 2 đô Vé 7 ngày 7 đô Vé 30 ngày 25 đô

Vì vậy, nếu đầu vào là ngày =[1, 3, 5, 6, 28], thì đầu ra sẽ là 9, vì chi phí thấp nhất có thể đạt được bằng cách mua vé 7 ngày ban đầu và sau đó là 1 ngày trôi qua vào ngày thứ 29.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• n:=tối đa ngày

• days:=một tập hợp mới từ ngày

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

• đối với tôi trong phạm vi từ 1 đến n + 1, hãy thực hiện

  • nếu tôi trong số ngày là khác 0, thì

    • nếu tôi> =30, thì

      • dp [i]:=tối thiểu là dp [i - 1] + 2, dp [i - 7] + 7, dp [i - 30] + 25

    • ngược lại khi i> =7 thì

      • dp [i]:=tối thiểu là dp [i - 1] + 2, dp [i - 7] + 7, 25

    • nếu không,

      • dp [i]:=tối thiểu là dp [i - 1] + 2, 7

  • nếu không,

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

• trả về dp [n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

[1, 3, 5, 6, 28]

Đầu ra

9