1. Climbing Stairs

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

Hint: To reach nth step, what could have been your previous steps? (Think about the step sizes)

Answer for n=5:

Starting at step 0, you have two choices — move 1 step (to step 1) or 2 steps (to step 2).

• From step 1, you can move to step 2 or step 3.

• From step 2, you can move to step 3 or step 4.

• From step 3, you can move to step 4 or step 5.

• From step 4, you can move to step 5 or step 6 — but since n = 5 is the limit, any path beyond step 5 is invalid.

You can perform a Depth-First Search (DFS) on this decision tree to explore all possible paths from step 0 to step 5.

If you look closely, the tree has same sub-structure for nodes- 2, 3 and 4. Instead of recomputing it each time like in recursion, it's effective to store the result in a 1D array.(memoization) 

Optimal sub structures

Top-down Solution:

Let’s start from the top (step 5) and work backward:

• Step 5: There’s only one way to reach step 5 from step 5 itself — by staying there. So we store 1 in the array.

• Step 4: From step 4, you can take 1 step to reach step 5, but taking 2 steps would exceed the limit (6 > 5). Hence, there’s only 1 way to reach step 5 from step 4.

• Step 3: From step 3, you can move 1 step to step 4 or 2 steps to step 5. The number of ways from step 3 = ways(4) + ways(5) = 1 + 1 = 2.

• Step 2: From step 2, you can go to step 3 or step 4. The total ways = ways(3) + ways(4) = 2 + 1 = 3.

• Step 1: From step 1, you can go to step 2 or step 3. The total ways = ways(2) + ways(3) = 3 + 2 = 5.

• Step 0: Finally, from step 0, you can go to step 1 or step 2. The total ways = ways(1) + ways(2) = 5 + 3 = 8.

If you observe the array, it's nothing but Fibonacci series!

Simple python code:

def climbStairs(n):
  one, two = 1,1
      for i in range(n-1):
          temp = one
          one = one+two
          two= temp
  return one