99클럽 코테 스터디 40일차 TIL + 오늘의 학습 키워드 746. 최소 비용 계단 오르기

ㅎㅇ·2024년 8월 30일
0

항해99 TIL

목록 보기
32/33
post-custom-banner

⭐ 문제

https://leetcode.com/problems/min-cost-climbing-stairs/description/

🧐 시도

class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];

    // 기저 사례: 첫 두 계단은 직접 올라갈 수 있음
    dp[0] = 0;
    dp[1] = 0;
    
    // 동적 프로그래밍으로 최소 비용 계산
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    }
    
    // 마지막 계단에 도달하는 최소 비용 반환
    return dp[n];
}

}

📝 풀이

dp 배열을 생성하여 각 계단까지의 최소 비용을 저장합니다.
첫 두 계단(인덱스 0과 1)은 비용 없이 시작할 수 있으므로 0으로 초기화합니다.
3번째 계단부터 시작하여 각 계단까지의 최소 비용을 계산합니다.
각 계단에 대해, 이전 계단에서 오는 경우와 전전 계단에서 오는 경우 중 최소 비용을 선택합니다.
마지막으로, 마지막 계단(n번째)에 도달하는 최소 비용을 반환합니다.

이 알고리즘은 주어진 제약 조건(2 <= cost.length <= 1000, 0 <= cost[i] <= 999)을 만족하며, 예시 1과 2의 결과를 정확히 계산할 수 있습니다.

profile
안녕하세요
post-custom-banner

0개의 댓글