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(2^n)

SpaceComplexity: O(n)

""" 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()

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)

SpaceComplexity: O(n)

""" 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()

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)

SpaceComplexity: O(1)

""" 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()

0746 - Min Cost Climbing Stairs

Solution 1 - Recursive (Brute Force)

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

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