Be the first user to complete this post

Add to List 
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 a child has to take n steps.
 At every step, the child has 3 options, to take 1 step, 2 steps, or 3 steps.
 So if the child takes 1 step then find the number of ways to complete n1 steps +1.
 Similarly, if the child takes 2 steps then find the number of ways to complete n2 steps +1.
 If the child takes 3 steps then find the number of ways to complete n3 steps +1.
 So total number of ways to complete n steps = No of ways to complete (n1)steps + No of ways to complete (n2)steps + No of ways to complete (n3)steps +1.
Using Recursion:
https://gist.github.com/thmain/e5caec8baebeaa6ffdf0
If we solve this problem using recursion then all the subproblems will be calculated repeatedly.
Using Dynamic Programming:
 We will solve it TopDown approach.
 We need to store the solutions for the subproblems in an array.
Code:
Output:
4
Also Read: