# 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:

 public class StepsPossiblePathsRecur { public int possibleWays(int n) { if (n < 1) { return 0; } return 1 + possibleWays(n – 1) + possibleWays(n – 2) + possibleWays(n – 3); } public static void main(String[] args) { // TODO Auto-generated method stub int n = 3; StepsPossiblePathsRecur s = new StepsPossiblePathsRecur(); System.out.println(s.possibleWays(n)); } }

view raw
PossibleWays.java
hosted with ❤ by GitHub

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:

 public class StepsPossiblePathsRecur { public int possibleWaysDyna(int n, int[] dyn) { if (n == 0) return 1; if (n < 0) return 0; if (dyn[n] > 0) { return dyn[n]; } dyn[n] = possibleWaysDyna(n – 1, dyn) + possibleWaysDyna(n – 2, dyn) + possibleWaysDyna(n – 3, dyn); return dyn[n]; } public static void main(String[] args) { // TODO Auto-generated method stub int n = 3; StepsPossiblePathsRecur s = new StepsPossiblePathsRecur(); int[] dyn = new int[n + 1]; System.out.println(s.possibleWaysDyna(n, dyn)); } }

Output:

`4`