746. Min Cost Climbing Stairs¶

• https://leetcode.com/problems/min-cost-climbing-stairs/

Recursion¶

• This solution hits TLE when run for large test cases

In [1]:

def min_cost_climbing_stairs(cost):

    # number of stairs
    n = len(cost)

    # this function will calculate the
    # minimum cost for all stairs except
    # the nth stair that is why when we call
    # solve() we call it with (n-1) and (n-2)
    def solve(n):
        if n < 0:
            return 0

        if n == 0 or n == 1:
            return cost[n]

        ans = min(solve(n - 1), solve(n - 2)) + cost[n]
        return ans

    # here we are at the nth step so we do not include the cost
    # we just want the cost we incurred in the previous set of steps
    ans = min(solve(n - 1), solve(n - 2))
    return ans

def min_cost_climbing_stairs(cost): # number of stairs n = len(cost) # this function will calculate the # minimum cost for all stairs except # the nth stair that is why when we call # solve() we call it with (n-1) and (n-2) def solve(n): if n < 0: return 0 if n == 0 or n == 1: return cost[n] ans = min(solve(n - 1), solve(n - 2)) + cost[n] return ans # here we are at the nth step so we do not include the cost # we just want the cost we incurred in the previous set of steps ans = min(solve(n - 1), solve(n - 2)) return ans

In [2]:

cost = [10, 15, 20]
min_cost_climbing_stairs(cost)

cost = [10, 15, 20] min_cost_climbing_stairs(cost)

Out[2]:

15

In [3]:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
min_cost_climbing_stairs(cost)

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] min_cost_climbing_stairs(cost)

Out[3]:

6

Recursion + Memoization¶

• All test cases passed

In [4]:

def min_cost_climbing_stairs_memo(cost):

    n = len(cost)

    # 1. 1D dp array till n including 0th index
    dp = [-1] * (n + 1)

    def solve(n):

        if n < 0:
            return 0

        if n == 0 or n == 1:
            return cost[n]

        # 3. if result exists in dp, return
        if dp[n] != -1:
            return dp[n]

        # 2. store results
        dp[n] = min(solve(n - 1), solve(n - 2)) + cost[n]

        return dp[n]

    ans = min(solve(n - 1), solve(n - 2))

    return ans

def min_cost_climbing_stairs_memo(cost): n = len(cost) # 1. 1D dp array till n including 0th index dp = [-1] * (n + 1) def solve(n): if n < 0: return 0 if n == 0 or n == 1: return cost[n] # 3. if result exists in dp, return if dp[n] != -1: return dp[n] # 2. store results dp[n] = min(solve(n - 1), solve(n - 2)) + cost[n] return dp[n] ans = min(solve(n - 1), solve(n - 2)) return ans

In [5]:

cost = [10, 15, 20]
min_cost_climbing_stairs_memo(cost)

cost = [10, 15, 20] min_cost_climbing_stairs_memo(cost)

Out[5]:

15

In [6]:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
min_cost_climbing_stairs_memo(cost)

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] min_cost_climbing_stairs_memo(cost)

Out[6]:

6

Tabulation - Bottom Up DP¶

• All test cases passed
• Note: The for loop goes upto n+1 here. It is because we are calling the solve function

    by passing `n-1` and `n-2`

In [7]:

def min_cost_climbing_stairs_dp(cost):

    # get nth stair
    n = len(cost)

    # 1. create 1D dp array
    dp = [-1] * (n + 1)

    def solve(n):
        # base cases
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

        return dp[n]

    ans = min(solve(n - 1), solve(n - 2))

    return ans

def min_cost_climbing_stairs_dp(cost): # get nth stair n = len(cost) # 1. create 1D dp array dp = [-1] * (n + 1) def solve(n): # base cases dp[0] = cost[0] dp[1] = cost[1] for i in range(2, n + 1): dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] return dp[n] ans = min(solve(n - 1), solve(n - 2)) return ans

In [8]:

cost = [10, 15, 20]
min_cost_climbing_stairs_dp(cost)

cost = [10, 15, 20] min_cost_climbing_stairs_dp(cost)

Out[8]:

15

In [9]:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
min_cost_climbing_stairs_dp(cost)

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] min_cost_climbing_stairs_dp(cost)

Out[9]:

6

Tabulation - Bottom Up DP - Slight optimization¶

• Passed all test cases.

• Here, we can do a little more optimization

  • Instead of just returning dp[n] we can return min(dp[n-1], dp[n-2])
  • check loop ending point, it goes till n because solve() gets called by n and not n-1

In [10]:

def min_cost_climbing_stairs_dp_opt(cost):

    # get nth stair
    n = len(cost)

    def solve(n):
        # 1. create 1D dp array
        dp = [-1] * (n + 1)

        # 2. base cases
        dp[0] = cost[0]
        dp[1] = cost[1]

        # this time we will have to go till n-1,
        # n-2 will be included in that as (n-1),(n-1), (n)
        for i in range(2, n):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

        # this print statement clears every doubt
        # when you dry run the code
        # print("dp: ", dp)
        # again here, we have not included the cost
        # of the nth step or stair
        ans = min(dp[n - 1], dp[n - 2])
        return ans

    ans = solve(n)

    return ans

def min_cost_climbing_stairs_dp_opt(cost): # get nth stair n = len(cost) def solve(n): # 1. create 1D dp array dp = [-1] * (n + 1) # 2. base cases dp[0] = cost[0] dp[1] = cost[1] # this time we will have to go till n-1, # n-2 will be included in that as (n-1),(n-1), (n) for i in range(2, n): dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] # this print statement clears every doubt # when you dry run the code # print("dp: ", dp) # again here, we have not included the cost # of the nth step or stair ans = min(dp[n - 1], dp[n - 2]) return ans ans = solve(n) return ans

In [11]:

cost = [10, 15, 20]
min_cost_climbing_stairs_dp_opt(cost)

cost = [10, 15, 20] min_cost_climbing_stairs_dp_opt(cost)

Out[11]:

15

In [12]:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
min_cost_climbing_stairs_dp_opt(cost)

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] min_cost_climbing_stairs_dp_opt(cost)

Out[12]:

6

Space optimization - incorrect solution¶

• Test cases failed

In [13]:

def min_cost_climbing_stairs_dp_space_opt(cost):

    n = len(cost)

    def solve(n):

        prev2 = cost[0]
        prev1 = cost[1]

        current = -1
        for i in range(2, n + 1):
            # only cost accumulation is happening
            # for the minimum path taken to reach the nth stair
            current = cost[i] + min(prev2, prev1)
            prev2 = prev1
            prev1 = current

        return prev1

    ans = min(solve(n - 1), solve(n - 2))

    return ans

def min_cost_climbing_stairs_dp_space_opt(cost): n = len(cost) def solve(n): prev2 = cost[0] prev1 = cost[1] current = -1 for i in range(2, n + 1): # only cost accumulation is happening # for the minimum path taken to reach the nth stair current = cost[i] + min(prev2, prev1) prev2 = prev1 prev1 = current return prev1 ans = min(solve(n - 1), solve(n - 2)) return ans

In [14]:

cost = [10, 15, 20]
min_cost_climbing_stairs_dp_space_opt(cost)

cost = [10, 15, 20] min_cost_climbing_stairs_dp_space_opt(cost)

Out[14]:

15

In [15]:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
min_cost_climbing_stairs_dp_space_opt(cost)

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] min_cost_climbing_stairs_dp_space_opt(cost)

Out[15]:

6

Space Optimized - correct solution¶

• Passed all test cases

In [16]:

def min_cost_climbing_stairs_space_opt(cost):

    n_stairs = len(cost)

    def solve(n):

        prev2 = cost[0]
        prev1 = cost[1]

        for i in range(2, n):
            current = cost[i] + min(prev1, prev2)
            prev2 = prev1
            prev1 = current

        return min(prev1, prev2)

    ans = solve(n_stairs)

    return ans

def min_cost_climbing_stairs_space_opt(cost): n_stairs = len(cost) def solve(n): prev2 = cost[0] prev1 = cost[1] for i in range(2, n): current = cost[i] + min(prev1, prev2) prev2 = prev1 prev1 = current return min(prev1, prev2) ans = solve(n_stairs) return ans

In [17]:

cost = [10, 15, 20]
min_cost_climbing_stairs_space_opt(cost)

cost = [10, 15, 20] min_cost_climbing_stairs_space_opt(cost)

Out[17]:

15

In [18]:

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
min_cost_climbing_stairs_space_opt(cost)

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] min_cost_climbing_stairs_space_opt(cost)

Out[18]:

6