[DP]99클럽 코테 스터디 38일차 TIL + 0747-min-cost-climbing-stairs

747. Min Cost Climbing Stairs

Easy

---

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

 

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

 

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

 

<내 코드>

* 1번째 방법

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:

        # 그리디 방법
        # 최소 비용 찾기
        total, i, = 0, (len(cost))
        while i >= 2:
            if cost[i - 2] <= cost[i - 1]: # 뒤쪽이 더 크면
                i -= 2 # 앞에 인덱스로
            elif cost[i - 2] > cost[i - 1]: # 앞쪽이 더 크면
                i -= 1
            print(i)
            total += cost[i]
    
        return total

 

- 그리디를 생각해서 마지막 인덱스에서 하나씩 역순으로 실시하였음

=> 하지만 그리디의 전형적인 문제는 지역적 문제만 해결가능하지, 그 다음에 대해서 생각하지 못하게 됨

[0,2,2,1] 이런 케이스에 대해서 정답은 2이지만, 나는 3이라고 최소비용이 못나오게 됨

 

- 그렇다고 그다음 순서까지 로직으로 짜기에는 매우 비상식 적임

=> 이럴수록 필요한게 DP

DP를 이용하면 tabulation으로 각각의 위치에서 최소비용이 저장되게 됨

 

* 2번째 방법

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
    # DP 방법 -> 점화식
        output = 0
        dp = [0 for _ in range(len(cost))]
        dp[0] = cost[0]
        dp[1] = cost[1]

        i = 2
        while i < len(cost) :
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
            i += 1

        output = min(dp[len(cost) - 1], dp[len(cost) - 2])
        return output

- 점화식을 어렵게 생각할 필요없이 이전값에 대해서 최소 비용을 계산하게 하는 것이 무엇인지를 생각하게 하면됨

 

 

<모범 사례> 

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

- 기존에는 공간복잡도 O(n)이었는데, 공간복잡도 O(1) 로 가능함

 

<보충 학습>

 

- DP 문제 해결 사고로직

 

• 문제를 읽고 이해합니다.
  • 문제의 목표와 조건을 명확히 파악합니다.
• 상태를 정의합니다.
  • 무엇을 구하려고 하는지, 그리고 이를 어떻게 배열이나 변수로 표현할지 결정합니다.
• 점화식을 도출합니다.
  • 현재 상태를 이전 상태와 연결하는 규칙을 찾습니다.
• 초기 조건을 설정합니다.
  • 점화식이 처음부터 적용될 수 있도록 필요한 초기값을 설정합니다.
• 최종 목표를 설정합니다.
  • 구하고자 하는 최종 값을 명확히 하여 답을 도출합니다.

- 예

 

• 상태 정의: dp[i] = i번째 계단까지 도달하는 최소 비용.
• 점화식: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
• 초기 조건: dp[0] = cost[0], dp[1] = cost[1]
• 최종 목표: min(dp[-1], dp[-2])