[LeetCode] Min Cost Climbing Stairs 자바

문제

 

 

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.

 

 

 

 

---

문제[번역]

 

cost[] 정수 배열이 주어집니다. 당신은 cost값을 이용해 계단을 1칸또는 2칸 올라갈 수 있습니다.

당신은 0번째 계단이나 1번째 계단에서 시작합니다.

계단 꼭대기에 올라가기 위한 최소 cost비용합을 구하세요.

 

 

 

 

---

 

Example 1

[10,15,20]

 

15

Example 2

[1,100,1,1,1,100,1,1,100,1]

6

 

 

---

제약조건

 

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

 

 

 

 

 

---

접근방법

어디서 많이 본듯한 흔한 dp문제입니다.

dp알고리즘을 이용해 각단계에서의 최솟값을 저장한 다음,

꼭대기에 도달할 수 있는 dp[size-1] 과 dp[size-2]중 작은 값을 리턴해줍니다.

 

 

 

---

코드

 

class Solution {
    public int minCostClimbingStairs(int[] cost) {
      int size = cost.length;
      int dp[] = new int[size+1];
      dp[0] = cost[0];
      dp[1] = cost[1];
      for(int i=2; i<size; i++){
        dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i];
      }
      return Math.min(dp[size-2],dp[size-1]);
    }
}

 

 

---

주의사항

 

x