Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python의 최소 비용 계단 오르기

<시간/>

계단이 있다고 가정하고 여기에서 i 번째 단계는 음이 아닌 비용 가치 비용[i]이 할당됩니다. 우리가 비용을 지불할 때, 우리는 한두 단계를 올라갈 수 있습니다. 우리는 바닥의 최상단에 도달하기 위한 최소 비용을 찾아야 하며, 인덱스 0의 단계부터 시작하거나 인덱스 1의 단계부터 시작할 수도 있습니다.

따라서 입력이 비용 =[12,17,20]과 같으면 출력은 17이 됩니다. 해당 비용을 지불하고 맨 위로 이동해야 하므로 1단계부터 시작하는 가장 저렴한 위치입니다.

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

  • dp :=비용과 크기가 같고 0으로 채워지는 배열
  • dp[0] :=비용[0]
  • 비용 크기>=2이면
    • dp[1] :=비용[1]
  • 범위 2에서 비용 - 1까지의 i에 대해, do
    • dp[i] :=비용[i] + 최소 dp[i-1], dp[i-2]
  • 최소 dp[-1], dp[-2] 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def minCostClimbingStairs(self, cost):
      dp = [0] * len(cost)
      dp[0] = cost[0]
      if len(cost) >= 2:
         dp[1] = cost[1]
      for i in range(2, len(cost)):
         dp[i] = cost[i] + min(dp[i-1], dp[i-2])
      return min(dp[-1], dp[-2])
ob = Solution()
print(ob.minCostClimbingStairs([12,17,20]))

입력

[12,17,20]

출력

17