계단이 있다고 가정하고 여기에서 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