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의 결과를 정확히 계산할 수 있습니다.