[LeetCode] 746 Min Cost Climbing Stairs-javascript

나의 풀이

var minCostClimbingStairs = function(cost) {
    
    
    const goalStair = cost.length
    let DP=[]
    DP[0] = 0;
    DP[1] = 0;
    DP[2] = Math.min(cost[0],cost[1])

    
    
    for (let i=3 ; i<= goalStair ; i++){
        let one = DP[i-2]+cost[i-2];
        let two = DP[i-1]+cost[i-1]
        DP[i] = Math.min(one,two)
        console.log(i,DP)
    }


    return DP[goalStair]
};

 

 

cost [10, 15, 20] 일때  나는 DP[3] 을 구할 것이다.

cost 주어진 비용이 표기된 계단을 오르는 최소 비용을 구하는 것이다.

DP[n] 을  n 계단에 도착하기 위해 필요한 최소비용이라고 가정한다.

 

계단은 1,2 단위로 오를 수 있기 때문에 DP[0], DP[1]을 오르는 데는 비용이 들지 않는다.

DP[0] = 0

DP[1] =  0

 

DP[2]에 오르는 비용은  아래 중 최솟값을 가지게 된다 .

min( 1번째 계단의 최소비용, 2번째 계단의 최소비용) 

 

 

DP[3] = min( DP[1] + cost[1] , DP[2]+cost[2] )

DP[3] 은 min( DP[1]최소비용+2번째 계단의 최소비용   ,  DP[2]최소비용+ 3번째 계단의 최소비용 )

 

이와 같은 방식으로 계단의 최소를 구해주면 성공!

 

 

관련 알고리즘 학습은 코드없는 프로그래밍의 DP 강의를 참조