LC 70 & LC 746

Solution to LeetCode 70 Climbing Stairs & LeetCode 746 Min Cost Climbing Stairs.

LeetCode 70

Climbing Stairs (Easy). [link]

The question is asking the number of distinct ways to climb to the top. There are two ways to reach the top, one is by climbing one step, the other is by climbing two steps. So the number of distinct ways to reach the top is the sum of the number of distinct ways to reach the last step and the number of distinct ways to reach the second to last step.

Define dp[i] as the number of distinct ways to climb to the ith staircase. Since we can either climb 1 or 2 steps, there are two ways to climb to the ith staircase, either from dp[i-1] by one step or from dp[i-2] by two steps. Therefore we have dp[i] = dp[i - 1] + dp[i - 2]. From this formula we know that the iteration is going forward from the beginning. The base cases are dp[0]=dp[1]=1 meaning that there is only 1 way to go to the first stair or stay there.

1] Recursion with and without memoization (TLE).

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n+1)
        dp[0],dp[1] = 1, 1
        def climb(n, dp):
            if n == 0 or n == 1: return 1
            if dp[n] != 0: return dp[n]
            dp[n] = climb(n-1, dp) + climb(n-2, dp)
            return dp[n]
        return climb(n, dp)

class Solution(object): # TLE
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0 or n == 1: return 1
        return self.climbStairs(n-1) + self.climbStairs(n-2)

2] Dynamic Programming with and without rolling array.

Time complexity O(n). Space complexity O(n) or O(1) if optimized.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a, b = 1, 1
        for i in range(n):
            a, b = b, a+b
        return a

3] 0-x Knapsack problem

Define dp[i] as the number of distinct ways to reach the top. The recurrence relation is dp[j] += dp[i-j]. The base case dp[0]=1, other values are 0.

Note that we want the number of permutations of steps (rather than combinations), meaning that step 1->2 and step 2->1 are different. Therefore, the outer for loop should iterate capacities, and the inner for loop should iterate items.

The time complexity O(n^2). The space complexity is O(n).

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[0]=1
        for j in range(n+1):
            for i in range(1,2+1):
                if j >= i:
                    dp[j] += dp[j-i]
        return dp[n]

LeetCode 746

Min Cost Climbing Stairs (Easy). [link]

This question is asking us to find the minimum cost to reach to the top of the floor, given an array of cost taken at ith staircase.

Define dp[i] as the min cost taken to reach the ith staircase. There are two ways to reach dp[i], either from dp[i-1] or from dp[i-2]. Whether choosing dp[i-1] or dp[i-2] depends on the which takes less cost, so we have dp[i-1] = min(dp[i-1], dp[i-2]) + cost[i]. The base cases are dp[0] = cost[0], dp[1] = cost[1].

1] Top-down recursive memoization

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        def recursion(i):
            if i <= 1: return 0
            if DP[i] != 0: return DP[i]
            DP[i] = min(recursion(i-1) + cost[i-1], 
                       recursion(i-2) + cost[i-2])
            return DP[i]
        DP = [0] * (len(cost)+1)
        return recursion(len(cost))

2] Bottom-up memoization

Time complexity O(n). Space complexity O(n).

There is no cost at the top of the floor, so we return the min aggregated cost of the final two staircases.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * n
        dp[0]= cost[0]
        dp[1]= cost[1]
        for i in range(2, n):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
        return min(dp[n-1], dp[n-2])

class Solution:
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: 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]