다이나믹 프로그래밍(계단 오르기)

문제: n개의 계단을 오르고자 한다. 한번에 1개, 2개씩의 계단을 오를수 있을때 총 몇가지 방벙으로 계단을 오를 수 있는가?

 

피보나치 수열 문제와 똑같다. 시작 지점만 다름.

다이나믹 프로그래밍(기초) (tistory.com)

다이나믹 프로그래밍(기초)

def climbStairs(n : int) -> int:
    dp_array = [0, 1, 2]
    for i in range(3, n+1):
        ith_way = climbStairs(i-1) + climbStairs(i-2)
        dp_array.append(ith_way)
    return dp_array[n]

 

문제: i번째 계단을 오르는 비용이 cost[i]로 주어졌다. 계단을 한번에 한칸 혹은 두칸씩만 오를수 있을때, 전체 계단을 오르는 최소 비용은 얼마인가.

from typing import List

def minCostStairs(cost:List[int]) -> int:
    dp_array = [0, 0]
    for idx in range(2, len(cost) + 1):
        minCost = min(dp_array[idx - 1] + cost[idx - 1], dp_array[idx - 2] + cost[idx - 2])
        dp_array.append(minCost)
        
    return dp_array[len(cost)]

stair_cost = [1,2,4,6,2,4,6,1]
print(minCostStairs(cost=stair_cost))

 

출처 : (5) 코딩테스트, 초급, 계단오르기 - YouTube