DP 아자아자 ⚒

DP 문제를 잘 푸는 방법

1. 점화식을 찾는다.
2. 찾은 점화식이 맞는지 표를 그려서 확인해본다. (수식으로 못 찾아도 표만 잘 되면 ㅇㅋ)

746. Min Cost Climbing Stairs

description

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Solution

code

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        top = len(cost)
        step = [0] * top
        step[0] = cost[0]
        step[1] = cost[1]
        
        for i in range(2, top) :
            step[i] = min(step[i-2], step[i-1]) + cost[i]
        
        return min(step[top-1], step[top-2])

logic

주어진 cost 배열 가장 끝(top)에 0이 있다고 가정했을 때, top에 도달하기 위한 min cost는 top-1, top-2 중 min 값이다. top-1, top-2의 값들을 찾기 위해서는 그 전에 DP를 통해 값을 누적해가야 한다.

누적하는 부분이 for loop인데 0과 1은 처음 시작하는 부분이므로 값을 바로 넣어두고 인덱스 2부터 순회한다.

최종적으로는 step[top-1], step[top-2] 중 최소값을 리턴한다.