처음으로 90%를 넘긴 문제.. 신기하다
문제
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1: Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost[1], pay that cost and go to the top. Example 2: Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3]. Note: cost will have a length in the range [2, 1000]. Every cost[i] will be an integer in the range [0, 999].
풀이
배열의 원소가 주어질때 계단을 1칸, 2칸 중 선택해서 오를 수 있다. 계단을 오를때 마다 비용이 발생하는데 목적지에 도착할때까지 최소 비용으로 도착해야 한다는게 문제이다.
생각의 흐름
문제를 딱 보자마자 아 그냥 dp로 풀면 간단하겠네.. 라고 생각했지만
완전 간단한 문제는 아니었다. 의외로 좀 생각을 하게 만들었던 문제
dp[i] 를 i에 도달하기 까지의 최소 비용으로 놓자. 그러면 dp[i]는 dp[i-2]에서 cost[i]를 밟은거랑 dp[i-1]에서 cost[i]를 밟는 두가지 경우에서만 i번째 계단에 도착 할 수 있다.
그래서 그냥 단순히 for문으로 문제를 풀면 되는데, 문제는 마지막 부분에서 있었다.
계단은 무조건 한칸 또는 두칸을 이동해야 하기 떄문에 마지막에서 -1번째 계단에서 게임을 끝낼수도있고
마지막 계단에서 게임이 끝날수도 있다. 이걸 고려해서 결과를 리턴해야한다.
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
const memo = [],
len = cost.length;
for (let i = 0; i < len; i++) {
if (i <= 1) {
memo[i] = cost[i];
} else {
memo[i] = Math.min(memo[i - 2] + cost[i], memo[i - 1] + cost[i]);
}
}
return Math.min(memo[len - 1], memo[len - 2]);
};