Min Cost Climbing Stairs

Leetcode Problem 746: Min Cost Climbing Stairs

Problem Summary

You are given an integer array where each element represents the cost of stepping on that stair. Once you pay the cost at a step, you can climb either one or two steps forward. You may start from step 0 or step 1. Return the minimum total cost to reach the top of the staircase (one step beyond the last index). The array has between 2 and 1,000 elements, and each cost is a non-negative integer up to 999.

Techniques

• Array
• Dynamic Programming

Solution

function minCostClimbingStairs(cost: number[]): number {
    const dpCosts = [...cost]

    for (let i = cost.length - 1; i >= 0; i--) {
        dpCosts[i] = dpCosts[i] + Math.min(dpCosts[i + 1] ?? 0, dpCosts[i + 2] ?? 0)
    }

    return Math.min(dpCosts[0], dpCosts[1])
};

console.log(minCostClimbingStairs([10, 15, 20])) // 15
console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) // 6