> [!META]- Inline Metadata > [tags:: #career #concepts/programming/algorithms/dynamic-programming] > [project group:: Neetcode 150] > [difficulty:: easy] > [status:: done] > [link:: https://leetcode.com/problems/climbing-stairs/] > [up:: [[Leetcode MOC]]] ## Problem You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top? ### Example 1 **Input:** n = 2 **Output:** 2 **Explanation:** There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps ### Example 2 **Input:** n = 3 **Output:** 3 **Explanation:** There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step **Constraints:** - `1 <= n <= 45` ## Solution **Think decision tree**. Base case is where result == number of steps. Another base case is where result > number of steps, return 0 in this case. ![[Pasted image 20221006210839.png]] Notice the repeated subtrees. How many ways from step 0 can we reach 5? Then, how many ways from step 1 can we reach 5? step 2? Step 3? So if you do just depth-first search, you are looking at $O(2^n)$. But since you have repeated decision trees, you can save the answer for each subtree once you've gotten there already. ![[Pasted image 20221006211147.png]] To do **true** DP solution, start at bottom, solving base case, and work way up tree. **Bottom-up DP**. Starting with 5, let's assume an empty array `dp` the size of the number of steps. We start with the 5th step. How many steps to get to the 5th step from the 5th step? 0. So `dp[5] = 1`. Next, at 4, you can take one step and get you to 5, or two steps to get you to 6, which gets you out of bounds. So here, there is just one way. `dp[4] = 1`. Now at 3, where we have a subproblem: if you take 2 steps, you're at 5, but if you take 1 step, you're at subproblem 4 (`dp[4]`). So: $ dp[3] = dp[4] + dp[5] = 1 + 1 = 2 $ So what about `dp[2]`? $ dp[2] = dp[3] + dp[4] = 2 + 1 = 3 $ We are using the next two solutions because you can take one step or two. ### Mine #### Python ```python def climb_stairs(n: str) -> int: solutions = [] for i in range(n + 1): if i == 0 or i == 1: solutions.append(1) continue solutions.append(solutions[i-1] + solutions[i-2]) return solutions[-1] ``` We don't even need an array here. We can just store the initial variables into `one` and `two` then shift them $n - 1$ times. ```python def climb_stairs_2(n: str) -> int: one, two = 1, 1 for i in range(n - 1): temp = one one = one + two two = temp # two is now the old value of one return one ``` #### Rust ### LC's ## Things I Learned ## Scratchpad