Python에서 하루 종일 여행하기 위한 최소 버스 요금을 찾는 프로그램?

<시간/>

매일 버스를 타야 하는 날짜라는 정렬된 숫자 목록이 있다고 가정합니다. 우리는 하루 종일 여행하는 데 소요되는 최저 비용을 찾아야 합니다. 버스 승차권은 3종류가 있습니다. 2달러에 1일 이용권 7달러에 7일 이용권 25달러에 30일 이용권

따라서 입력이 일 =[1, 3, 5, 6, 28]인 경우 출력은 9가 됩니다. 처음에는 7일 패스를 구입한 다음 1- 29일 1일권.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

n :=최대 일수
일 :=일의 새로운 세트
dp :=[0] *(n + 1)
범위 1에서 n + 1까지의 i에 대해 수행
- i in days가 0이 아닌 경우
  - 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]