LC70. Climbing Stairs

DP: DFS with Memoization

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = {}
 
        def dfs(i = 0):
            if i == n:
                return 1
            elif i > n:
                return 0
 
            if i in dp:
                return dp[i]
 
            dp[i + 1] = dfs(i + 1)
            dp[i + 2] = dfs(i + 2)
 
            return dp[i + 1] + dp[i + 2]
        
        return dfs()

Complexity

Time: $O(n)$ — with memoization, we don’t need go through all $2^n$ nodes of the tree, just the height
Space: $O(n)$

Pure DP: Bottom-up approach (Optimal)

class Solution:
    def climbStairs(self, n: int) -> int:
        # By analyzing bottom-up DP approach, we can conclude that the answer
        # would be the nth Fibonacci number (excluding 0).
 
        l, r = 1, 0
        total = 0
 
        while n > 0:
            total = l + r
            l, r = total, l
            n -= 1
        
        return total

Complexity

Time: $O(n)$
Space: $O(1)$

Notes

Start from the base case (i.e $n$) and go backwards. Suppose $n=5$, we’ll construct an array and start from this last case. We’ll ask: how many ways can we get to $5$? The answer since we’re already at $5$ would be $1$ and we’ll go to the previous step and ask the same question again. We can jump either $1$ or $2$ steps but we can only get to $5$ by jumping a single step. So, the no. of ways at $n=4$ is also $1$. From step $3$, we can either jump $1$ or $2$ steps and if we do so, we get to steps $4$ and $5$ respectively. But we already calculated the count at both of these steps so $resul{t}_{step3}=resul{t}_{step4}+resul{t}_{step5}$. If we continue, we’ll notice the following pattern:

$$\begin{array}{c}\begin{array}{cccccc}8& 5& 3& 2& 1& 1\end{array}\\ \begin{array}{cccccc}0& 1& 2& 3& 4& 5\end{array}\end{array}$$

…which resembles part of the Fibonnacci Sequence. So the answer would be the n^th Fibonacci number.