LC 746 - Min Cost Climbing Stairs

Question

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15

Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top. The total cost is 15.

Example 2:

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

Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Links

Question here and solution here

Solution

concept

If we solving from left to right:

dp[i] = minimum cost to reach step i (where i runs 0..n and n means the top).
You can start at step 0 or 1 for free → so dp[0]=dp[1]=0.
To reach i you must come from i-1 (one step) or i-2 (two steps). If you come from i-1 you must have paid cost[i-1]; if from i-2 you paid cost[i-2]

dp[i] = min(dp[i-1] + cost[i-1],  dp[i-2] + cost[i-2])

and we get dp[n] as the answer.

if we solving from right to left:

dp[i] = minimum cost from step i to reach the top (where i runs 0..n and n means the top).

code

class Solution:
	"""
	brute force
	"""
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        def dfs(i):
            if i >= len(cost):
                return 0
            return cost[i] + min(dfs(i + 1), dfs(i + 2))
        
        return min(dfs(0), dfs(1))
        
class Solution:
	"""
	top down (memozation)
	"""
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [-1] * len(cost)

        def dfs(i):
            if i >= len(cost):
                return 0
            if dp[i] != -1:
                return dp[i]

            dp[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
            return dp[i]
        
        return min(dfs(0), dfs(1))
        
class Solution:
	"""
	bottom up
	solving from left -> right
	"""
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        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]
        
class Solution:
	"""
	bottom up
	solving from right -> left
	"""
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)
        # the last index is the goal (i.e. we added one extra 0, from the above line)
        # the 2nd last index is the cost of the final step, since this is fixed, we have to pay this cost to reach from n - 1 to n
        # after that we can dp from left to right
        dp[-2] = cost[-1]

        for i in range(n-2, -1, -1):
            dp[i] = min(cost[i] + dp[i+1], cost[i]+dp[i+2])
		# choose from step 0 or step 1, whichever is the minimum
        return min(dp[0], dp[1])
        
class Solution:
	"""
	bottom up
	solving from right -> left
	space optimised
	"""
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cost.append(0) # [10, 15, 20] 0 -> add one 0 at the end, this is the goal

        for i in range(len(cost) - 3, -1, -1): # start from 3rd last, i,e, 15, and don't touch [20, 0]
            cost[i] = min(cost[i]+cost[i+1], cost[i]+cost[i+2])

        return min(cost[0], cost[1])

Complexity

time: $O(n)$
space: $O(n)$