cleanUrl: /posts/min-cost-climbing-stair-dp-strategy
DP 문제를 풀고싶어서 접근했던 문제인데 점화식을 찾아내는걸 보니 어느정도 감을 잡은것 같기도 하다
Min Cost Climbing Stairs - LeetCode
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.
계단 하나를 오를때 비용이 발생하고, 한번에 하나 혹은 두개의 계단을 오를 수 있다.
[10, 15, 20] 이면 15만 지불하고 모든 계단을 다 오를 수 있는 것인데 가장 최소의 비용을 지불하고 계단을 전부 오르려면 어떻게 해야하는가?
나에게 가장 큰 힌트가 된 것은 이 예시이다
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
이렇게 각 단계별로 접근을 했다.
n)까지 오르려면 그 이전에 올라와야 하는 계단은 어디인가?n-1 이라면 n-1 이전에 어디까지 올라가야 할까?이렇게 접근하다 보니 점화식이 어느정도 만들어졌다.
n 번째 계단에 오르는 비용을 저장한 배열 pay 가 있을때 n번째 계단의 비용을 구하는 점화식은 다음과 같다
$pay[n] = min(pay[n-1], pay[n-2]) + cost[n]$
→ pay[n] 을 반환하면 되겠다고 생각했다.
주어진 예시 [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 의 비용 pay는 다음과 같다
[?, ?, 2, 3, 3, 103, 4, 5, 104, 6]