๋ฌธ์ ๋งํฌ
Min Cost Climbing Stairs - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
์ด๋์ ์ํ cost๊ฐ์ด ์์๋ก ๋ค์ด์๋ cost ๋ฐฐ์ด์ด ์ฃผ์ด์ง๋ cost ๋ฐฐ์ด์ ๋๊น์ง ๊ฐ๋๋ฐ ์์๋๋ ๋น์ฉ์ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
์กฐ๊ฑด : ํ๋ฒ์ index 1์นธ ๋๋ 2์นธ์ ๊ฑด๋ ์ ์๋ค.
์ ๊ทผ ๋ฐฉ๋ฒ
์ ํ์ ์ธ dp ๋ฌธ์ ์ด๋ค.
์ ํ์ => dp[i] += Math.min(dp[i-1], dp[i-2]) + cost[i]
dp[i-1], dp[i-2]๋ ํ์ฌ๊น์ง ์ง๋ถํ ๋น์ฉ์ด๊ณ , cost[i]๋ ํ์ฌ ์์น์์์ ๋น์ฉ์ด๋ค.
dp[0] = cost[0]; dp[1] = cost[1]; for(let i = 2; i < cost.length; i++){ dp[i] += Math.min(dp[i-1], dp[i-2]) + cost[i]; }โ
ํ ์คํธ์ผ์ด์ค๋ฅผ ํตํด ์๋ฅผ ๋ค๋ฉด
[1,100,1,1,1,100,1,1,100,1]์ ์ ํ์์ ํตํด ๊ฐ์ ๋์ถํ๋ฉด ์๋์ ๊ฐ์ ๊ฐ์ด ๋์จ๋ค.
[1, 100, 2, 3, 3, 103, 4, 5, 104, 6]
โป ๋ค๋ฅธ ํ์ด
dp ๋ฐฐ์ด์ ๋ฐ๋ก ์์ฑํ์ง ์๊ณ ๋ค์์๋ถํฐ ๊ฐ์ ์ฐพ๋ ๋ฐฉ๋ฒ์ ๋ฐ๊ฒฌํ์๋ค.
for (let i = cost.length - 3; ~i; i--){ cost[i] += Math.min(cost[i+1], cost[i+2]) }โ
๋ฐ๋ก ๋ฐฐ์ด์ ์์ฑํ์ง ์์ ๋ฉ๋ชจ๋ฆฌ ํจ์จ์ฑ์ด ๋ ์ข์ ์ฝ๋์ด๋ค.
[1,100,1,1,1,100,1,1,100,1]์ ์ฝ๋๋ฅผ ๋๋ฆฌ๋ฉด ์๋์ ๊ฐ์ ๊ฐ์ด ๋์จ๋ค.
[6, 105, 5, 5, 4, 102, 3, 2, 100, 1]
// ๋์ ํ์ด
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
let dp = new Array(cost.length).fill(0);
dp[0] = cost[0];
dp[1] = cost[1];
for(let i = 2; i < cost.length; i++){
dp[i] += Math.min(dp[i-1], dp[i-2]) + cost[i];
}
return Math.min(dp[cost.length-1], dp[cost.length-2])
};
// ๋ค๋ฅธ ํ์ด
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
for (let i = cost.length - 3; ~i; i--){
cost[i] += Math.min(cost[i+1], cost[i+2])
}
return Math.min(cost[0], cost[1])
};
'์ฝ๋ฉํ ์คํธ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] Matchsticks To Square (0) | 2022.07.12 |
---|---|
[LeetCode] Combination Sum (0) | 2022.07.11 |
[LeetCode] Single Number (0) | 2022.07.09 |
[LeetCode] Fibonacci Number (0) | 2022.07.06 |
[LeetCode] Longest Consecutive Sequence (0) | 2022.07.05 |