Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0746 - Min Cost Climbing Stairs
    0746 - Min Cost Climbing Stairs
    0746 - Min Cost Climbing Stairs
    0746 - Min Cost Climbing Stairs

    0746 - Min Cost Climbing Stairs

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/min-cost-climbing-stairs/

    Solution 1 - Recursive (Brute Force)

    Starting from either step 0 or step 1, recursively compute the minimum cost to reach the top by choosing to climb one or two steps at each position. Return the minimum of starting from index 0 vs index 1.

    TimeComplexity:O(2n)TimeComplexity: O(2^n)TimeComplexity:O(2n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Dynamic Programming (Bottom-Up, O(n) Space)

    Use a DP array where dp[i] represents the minimum cost to reach step i. Build the array bottom-up. The answer is the minimum cost to reach just past the last step.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 3 - Dynamic Programming (Bottom-Up, O(1) Space)

    Same bottom-up approach but instead of maintaining a full DP array, only track the previous two values since each step only depends on the two preceding steps.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0746.1 - Solution 1 - Recursive Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        """Min Cost Climbing Stairs Function"""

        def helper(i: int) -> int:
            if i >= len(cost):
                return 0
            return cost[i] + min(helper(i + 1), helper(i + 2))

        return min(helper(0), helper(1))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().minCostClimbingStairs([10, 15, 20]))
    print(Solution().minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0746.2 - Solution 2 - Bottom-Up DP """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        """Min Cost Climbing Stairs Function"""
        n = len(cost)
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[n]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().minCostClimbingStairs([10, 15, 20]))
    print(Solution().minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0746.3 - Solution 3 - Space-Optimized Bottom-Up DP """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        """Min Cost Climbing Stairs Function"""
        prev2, prev1 = 0, 0
        for i in range(2, len(cost) + 1):
            curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
            prev2, prev1 = prev1, curr
        return prev1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().minCostClimbingStairs([10, 15, 20]))
    print(Solution().minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()