#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/min-cost-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/dynamic-programming-fundamentals/min-cost-implementation

Repovive

LeetCode 746 Min Cost Climbing Stairs - Implementation - Dynamic Programming Fundamentals | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 746 Min Cost Climbing Stairs - Implementation

Full solution

function minCostClimbingStairs(cost)
    n := length of cost
    dp := array of size (n + 1)
    dp[0] := 0
    dp[1] := 0
    for i from 2 to n
        dp[i] := min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    return dp[n]

You can shrink this to $O(1)$ space by tracking only prev1 and prev2, just like Fibonacci. This is your first cost minimization DP.

The code implements the recurrence relation directly. corresponds to part of the formula. To verify your understanding, pick a small example and trace through the code by hand. Write down the value of each variable at each step. This builds intuition that helps When face new problems.

Time: $O(n)$ . Space: $O(1)$ .