This post is completed by 3 users

  • 1
 Add to List
Beginner

146. 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:

  1. Say a child has to take n steps.
  2. At every step, the child has 3 options, to take 1 step, 2 steps, or 3 steps.
  3. So if the child takes 1 step then find the number of ways to complete n-1 steps +1.
  4. Similarly, if the child takes 2 steps then find the number of ways to complete n-2 steps +1.
  5. If the child takes 3 steps then find the number of ways to complete n-3 steps +1.
  6. 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.

Output:

4

Related Problems: