Min Cost Climbing Stairs

easy

Last Updated - 12/09/2024

Problem Statement Solution 1: Using a Hash Map for Memoization Solution 2: Using Dynamic Programming with Full Table Solution 3: Simple Recursive Approach Solution 4: Recursive Approach with Memoization Solution 5: Dynamic Programming (Space Optimization) Solution 6: Dynamic Programming (Tabulation) Solution 7: Using a Map for Memoization Solution 8: Using Combination of Recursive and Iterative Approach Solution 9: Using Sliding Window Technique Solution 10: Recursive Approach with Explicit Stack More Problems Solutions

Problem Statement

You are given an integer array cost where cost[i] represents the cost associated with stepping on the i-th stair of a staircase. You have the option to either start from the first stair (index 0) or the second stair (index 1). From any stair, you can either move up one step or two steps.

The goal is to calculate the minimum cost required to reach the top of the staircase. The top of the staircase is considered to be beyond the last stair, so your solution should ensure that you can climb to the end of the array from either the last stair or the second-to-last stair.

Example 1

Input: cost = [10,15,20]

Output: 15

Example 2

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Solution 1: Using a Hash Map for Memoization

function minCostHashMap(cost) {
    const memo = new Map();

    function dp(i) {
        if (i < 0) return 0;
        if (i === 0 || i === 1) return cost[i];
        if (memo.has(i)) return memo.get(i);
        const result = cost[i] + Math.min(dp(i - 1), dp(i - 2));
        memo.set(i, result);
        return result;
    }

    const n = cost.length;
    return Math.min(dp(n - 1), dp(n - 2));
} 

const cost1 = [10,15,20];
minCostHashMap(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostHashMap(cost2);  //output: 6

Solution 2: Using Dynamic Programming with Full Table

function minCostFullTable(cost) {
    const dp = Array(cost.length).fill(0);
    dp[0] = cost[0];
    dp[1] = cost[1];

    for (let i = 2; i < cost.length; i++) {
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
    }

    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
} 

const cost1 = [10,15,20];
minCostFullTable(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostFullTable(cost2);  //output: 6

Solution 3: Simple Recursive Approach

function minCostRecursive(cost) {
    function dp(i) {
        if (i < 0) return 0;
        if (i === 0 || i === 1) return cost[i];
        return cost[i] + Math.min(dp(i - 1), dp(i - 2));
    }

    const n = cost.length;
    return Math.min(dp(n - 1), dp(n - 2));
} 

const cost1 = [10,15,20];
minCostRecursive(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostRecursive(cost2);  //output: 6

Solution 4: Recursive Approach with Memoization

function minCostMemoization(cost) {
    const memo = {};

    function dp(i) {
        if (i < 0) return 0;
        if (i === 0 || i === 1) return cost[i];
        if (memo[i] !== undefined) return memo[i];
        memo[i] = cost[i] + Math.min(dp(i - 1), dp(i - 2));
        return memo[i];
    }

    const n = cost.length;
    return Math.min(dp(n - 1), dp(n - 2));
} 

const cost1 = [10,15,20];
minCostMemoization(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostMemoization(cost2);  //output: 6

Solution 5: Dynamic Programming (Space Optimization)

function minCostSpaceOptimized(cost) {
    const n = cost.length;
    let [prev1, prev2] = [cost[0], cost[1]];

    for (let i = 2; i < n; i++) {
        const current = cost[i] + Math.min(prev1, prev2);
        [prev1, prev2] = [prev2, current];
    }

    return Math.min(prev1, prev2);
} 

const cost1 = [10,15,20];
minCostSpaceOptimized(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostSpaceOptimized(cost2);  //output: 6

Solution 6: Dynamic Programming (Tabulation)

function minCostTabulation(cost) {
    const n = cost.length;
    const dp = Array(n).fill(0);
    dp[0] = cost[0];
    dp[1] = cost[1];

    for (let i = 2; i < n; i++) {
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
    }

    return Math.min(dp[n - 1], dp[n - 2]);
} 

const cost1 = [10,15,20];
minCostTabulation(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostTabulation(cost2);  //output: 6

Solution 7: Using a Map for Memoization

function minCostMapMemoization(cost) {
    const memo = new Map();

    function dp(i) {
        if (i < 0) return 0;
        if (i === 0 || i === 1) return cost[i];
        if (memo.has(i)) return memo.get(i);
        const result = cost[i] + Math.min(dp(i - 1), dp(i - 2));
        memo.set(i, result);
        return result;
    }

    const n = cost.length;
    return Math.min(dp(n - 1), dp(n - 2));
} 

const cost1 = [10,15,20];
minCostMapMemoization(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostMapMemoization(cost2);  //output: 6

Solution 8: Using Combination of Recursive and Iterative Approach

function minCostHybrid(cost) {
    const dp = Array(cost.length).fill(0);
    dp[0] = cost[0];
    dp[1] = cost[1];

    for (let i = 2; i < cost.length; i++) {
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
    }

    return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
} 

const cost1 = [10,15,20];
minCostHybrid(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostHybrid(cost2);  //output: 6

Solution 9: Using Sliding Window Technique

function minCostSlidingWindow(cost) {
    let prev1 = cost[0];
    let prev2 = cost[1];

    for (let i = 2; i < cost.length; i++) {
        const current = cost[i] + Math.min(prev1, prev2);
        prev1 = prev2;
        prev2 = current;
    }

    return Math.min(prev1, prev2);
} 

const cost1 = [10,15,20];
minCostSlidingWindow(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostSlidingWindow(cost2);  //output: 6

Solution 10: Recursive Approach with Explicit Stack

function minCostExplicitStack(cost) {
    const stack = [{ index: 0 }, { index: 1 }];
    const costs = Array(cost.length).fill(Infinity);
    costs[0] = cost[0];
    costs[1] = cost[1];

    while (stack.length > 0) {
        const { index } = stack.pop();
        if (index >= cost.length) continue;
        if (index < cost.length - 1) {
            const nextCost = cost[index + 1] + Math.min(costs[index], costs[index + 1]);
            if (nextCost < costs[index + 1]) {
                costs[index + 1] = nextCost;
                stack.push({ index: index + 1 });
            }
        }
        if (index < cost.length - 2) {
            const nextCost = cost[index + 2] + Math.min(costs[index], costs[index + 2]);
            if (nextCost < costs[index + 2]) {
                costs[index + 2] = nextCost;
                stack.push({ index: index + 2 });
            }
        }
    }

    return Math.min(costs[cost.length - 1], costs[cost.length - 2]);
} 

const cost1 = [10,15,20];
minCostExplicitStack(cost1);  //output: 15 

const cost2 = [1,100,1,1,1,100,1,1,100,1];
minCostExplicitStack(cost2);  //output: 6