dp 계단오르기최소비용질문입니다.

Question

경우의 수 문제에서는 memo[i]가 i번째 계단까지 도달하는 방법의 수를 저장했다.

최소 비용 문제에서는 memo[i]가 i번째 계단까지 도달하는 총 비용을 저장했다.

그렇다면 memo[i]가 이미 최소 비용을 저장하고 있다면, 왜 cost[i]까지 더해야 하나요?

memo[i] = min(memo[i-1], memo[i-2]) + cost[i]

계단 오르기 경우의 수 문제가

당신은 계단을 오르고 있습니다. n꼭대기에 도달하려면 단계가 필요합니다.

매번 당신은 오르 1거나 2계단을 오를 수 있습니다. 정상까지 올라갈 수 있는 뚜렷한 방법은 몇 가지입니까?

memo[i]=i가 3이라고 한다면 3까지 도달할 수 있는 방법을 저장하는것이고.

계단오르기 최소비용문제에서는 memo[i]=i가 3이라고 한다면 3까지 도달할 수 있는 비용을 저장하는것이라 생각하는데요.

아래는 최소 비용 문제 코드입니다

class Solution(object):
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        if n == 2:
            return min(cost)  # 계단이 두 개라면, 더 싼 비용을 선택
        
        # DP 배열 초기화
        memo = {}
        memo[0] = cost[0]
        memo[1] = cost[1]
        
        # 점화식을 이용하여 최소 비용 계산
        for i in range(2, n):
            memo[i] = min(memo[i-1], memo[i-2]) + cost[i]  # 불필요한 비교 제거

        # 마지막 계단을 오르지 않아도 되므로, 마지막 두 개 중 최소값 반환
        return min(memo[n-1], memo[n-2])

[노씨데브 코치] 구운햄 · Answer

안녕하세요. zzzzz님.

질문주신 두 문제 Climbing Stairs와 Min Cost Climbing Stairs는 비슷하지만 문제 요구사항에 있어 차이가 있습니다.

Climbing Stairs의 경우 목표와 점화식은 다음과 같습니다.

목표: 각 계단에 도달할 수 있는 “방법의 수”를 구하는 것.

점화식: memo[i] = memo[i-1] + memo[i-2]

여기서, memo[i]는 i번째 계단에 도달하는 데 가능한 모든 경로의 “개수”를 저장합니다.

계단을 밟는 행위 자체에 추가 비용이나 값이 없으므로, 단순히 이전 계단들의 방법의 수를 합산합니다.

반면 Min Cost Climbing Stairs는 이렇습니다.

목표: 각 계단에 도달하는 데 드는 최소 비용을 구하는 것.

점화식: memo[i] = min(memo[i-1], memo[i-2]) + cost[i]

여기서 memo[i]는 i번째 계단까지 도달하는 총 비용을 저장합니다.

그럼 왜 cost[i]를 더해야 할까요?

i번째 계단에 도달할 때 반드시 cost[i] 만큼의 비용을 지불해야 하기 때문입니다.

즉, i번째 계단을 밟는 행위 자체가 비용을 발생시킵니다.

따라서 이전 계단까지 도달하는 데 드는 최소 비용(즉, memo[i-1] 혹은 memo[i-2])에 현재 계단의 비용 cost[i]를 더해주어야 i번째 계단까지의 총 비용이 계산됩니다. 어떤 계단에 도달하는 비용을 누적해야 하므로, 계단마다 발생하는 추가 비용인 cost[i]를 반드시 포함시켜야 합니다.

반면 Climbing Stairs에서는 어떤 계단에 도달하는 경우의 수만 기록하면 되므로, 계단을 밟는 행위에 별도의 값(비용)을 더할 필요가 없습니다. 단순히 해당 위치에 도달할 수 있는 경우의 수를 구하는 것이 전부입니다.

추가적인 질문이 있다면 편하게 남겨주시기 바랍니다.

감사합니다.

인프런 커뮤니티 질문&답변

dp 계단오르기최소비용질문입니다.