# Dynamic Programming – Stairs Climbing Puzzle

**Objective: **A child is climbing up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can jump up the stairs.

**Example:**

Number of stairs : 3 Number of ways = 4 ( {1,1,1}, {1,2}, {2,1}, {3} )

**Approach:**

- Say child has to take n steps.
- At every step the child has 3 options, to take 1 step, 2 step or 3 steps.
- So if child take 1 step then find the number of ways to complete n-1 steps +1.
- Similarly if child take 2 steps then find the number of ways to complete n-2 steps +1.
- If child take 3 step then find the number of ways to complete n-3 steps +1.
- So total
*number of ways to complete n steps = No of ways to complete (n-1)steps + No of ways to complete (n-2)steps + No of ways to complete (n-3)steps +1**.*

**Using Recursion:**

If we solve this problem using recursion then all the sub-problems will be calculated repeatedly.

**Using Dynamic Programming:**

- We will solve it Top-Down approach.
- We need to store the solutions for the sub problems in an array.

**DP Code:**

**Output**:

4