Climbing Stairs
You are climbing a stair case. It takes n steps to reach to 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: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 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: The point to observe here is that while climbing stairs, you can take either 1 or 2 steps. So for every step that you climb, you have two options in front of you to choose from i.e., 1 step or 2 step. This is a typical case of recursion where in you let the system decide the number of ways to climb the stairs by writing minimal code. The entire problem is broken down into sub-problems and you will encounter similar sub-problems. So to increase the efficiency of the solution, we can store the outpu...