[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.
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
숫자로 이루어진 배열이 주어진다.
배열의 각 index는 계단의 위치를 의미하고, 값은 그 계단을 밟고 올라가는 데 드는 코스트를 뜻한다.
계단은 한 번에 1개 또는 2개씩 오를 수 있고, 끝까지 올라가는게 목표다!
이 때, 맨 꼭대기(배열의 끝)까지 올라갈 때까지 드는 최소 코스트를 구하는 문제.
var minCostClimbingStairs = function(cost) {
// 0, 1 -> +1 , +2 의 모든 경우의 수
const costs = new Set();
const stepUp = (i, total) => {
if(cost[i] == undefined){
costs.add(total);
return;
}
total = total + cost[i];
stepUp(i+1, total);
stepUp(i+2, total);
}
stepUp(0, 0);
stepUp(1, 0);
return Math.min(...costs);
};
카테고리가 DP인데 어쩌다 보니 재귀로 풀어 버렸다. 이렇게 해도 되지 않을까? 싶어서ㅋㅋㅋ
트리 탐색하듯이 모든 경우의 수를 다 따지는 식이다.
대부분의 케이스는 넘어갔는데 너무 비효율적인 구조다 보니 결국 Time Exceeded 이슈로 통과되지 않았음^_ㅠ
재귀가 진짜 비효율적일 때는 끝없이 떨어지는구나 싶다.. 물론 내가 제대로 못 짠 것도 있겠지만.
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
let pprev = cost[0];
let prev = cost[1];
let curr = 0;
for(let i=2; i < cost.length; i++){
curr = cost[i] + Math.min(prev, pprev);
pprev = prev;
prev = curr;
}
return Math.min(pprev, prev);
};
그래서 DP로 푼 다른 해답...
prev는 한 칸 전까지의 총 cost, pprev는 두 칸 전까지의 총 cost를 의미한다.
첫 시작만 제외하면 사실상 더 적은 코스트를 골라서 올라갈 수 있으니, 골라서 올라가면 된다ㅋㅋㅋ
하지만 2칸 뒤보다 4칸 뒤가 훨씬 더 코스트가 낮을 경우를 대비해서 이전과 그 이전까지의 값을 저장한다.
그리고 마지막에 Math.min을 쓰는 이유는, 맨 꼭대기까지 도착할 수 있는 방법도 두가지이기 때문이다.
한 칸 전 + 한 칸 이거나, 두 칸 전 + 두 칸 일 수 있으니...
DP 정말 편하구나~
