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));
}
}

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

17 thoughts on “Dynamic Programming – Stairs Climbing Puzzle”

  1. Approavh should be updated to => So total num­ber of ways to com­plete n steps = No of ways to com­plete (n-1)steps + No of ways to com­plete (n-2)steps + No of ways to com­plete (n-3)steps +1

    Reply
  2. you are not using the dyn array to store anything. here is the solution.

    public int poosibleWaysDyna(int n, int[] dyn) {
    if (n 0) {
    if (dyn[n]==0){
    dyn[n] = 1 + poosibleWaysDyna(n – 1, dyn) + poosibleWaysDyna(n – 2, dyn)
    + poosibleWaysDyna(n – 3, dyn);
    }
    }
    return dyn[n];
    }

    Reply
  3. what is the +1 for ? shouldn’t the recurrence relation be dyn[n] = poosibleWaysDyna(n – 1, dyn) + poosibleWaysDyna(n – 2, dyn) + poosibleWaysDyna(n – 3, dyn);

    Reply
    • Hi Harsh,

      +1 is for the step we are taken already. If you look at the recurrence relation, we are solving it for n-1, n-2, n-3. That means child has taken already one step (either 1 step or 2 step or 3 step and we are solving the remaining steps recursively). so we add +1. let me know if you need more clarity.

      Reply
      • Why is not dyn[n] = poosibleWaysDyna(n – 1, dyn) + poosibleWaysDyna(n – 2, dyn) + poosibleWaysDyna(n – 3, dyn)+3? I mean 3 stands for the last step. It can be 1 step, 2 step2, or 3 step3 corresponding to poosibleWaysDyna(n – 1, dyn),poosibleWaysDyna(n – 2, dyn) and poosibleWaysDyna(n – 3, dyn) respectively. So the last step can have 3 types. Why do you consider 3 kinds of last step as only 1?

        Reply
  4. how is this dynamic at all? You are still recursively calling different functions. The whole idea is to save spae and time and that is not being done here in either approach.

    Reply
  5. This gives incorrect output for n = 4.
    There are only 7 possible ways for 4 stairs: 1111,112,121,211,13,31,22 but your solution gives the value 8.

    Reply
  6. You do not +1 to the result. The recurrence relation is just ways(n-3) + ways(n-2) + ways(n-1).
    In your approach, you are confusing the number of ways vs the additional step taken to reach N. Taking the additional step contributes to EACH of the step combination in each way, but does NOT contribute to the total number of ways it takes.

    example:
    First, let’s define the base cases for N=1,2,3 respectively.
    Note: we are using alphabets to uniquely identify the actual combinations.

    If N = 1, there’s 1 way to reach N.
    the actual combinations are:
    a. 1

    if N=2, there’s 2 ways to reach N.
    the actual combinations are:
    b. 1,1
    c. 2

    if N=3, there’s 4 ways to reach N.
    the actual combinations are:
    d. 1,1,1
    e. 1,2
    f. 2,1
    g. 3

    Now when N=4, there will be 7 ways to reach N. The brackets in combinations below means the actual combinations we took from the case indicated in ‘possibleWays(N-1)’.

    possibleWays(N-1) case:
    (d. 1,1,1) + 1 = 1,1,1,1
    (e. 1,2) + 1 = 1,2,1
    (f. 2,1) + 1 = 2,1,1
    (g. 3) + 1 = 3,1

    possibleWays(N-2) case:
    (b. 1,1) + 2 = 1,1,2
    (c. 2) + 2 = 2,2

    possibleWays(N-3) case:
    (a. 1) + 3 = 1,3

    As you can see above, the additional step (either 1,2,3) is the actual step required to take to complete each way to attain the new N and NOT an additional way.

    Reply
  7. public static int getNumberOfPossibleWaysMath(int amount) {
    if (amount <= 0) return 0;
    if (amount <= 2) return amount;
    if (amount == 3) return 4;

    int minus3 = 1;
    int minus2 = 2;
    int minus1 = 4;
    int curr = 0;
    for(int i = 4; i <= amount; i++) {
    curr = minus3 + minus2 + minus1;
    minus3 = minus2;
    minus2 = minus1;
    minus1 = curr;
    }
    return curr;
    }

    Reply
  8. As the previous posters pointed out the formula used in this page is incorrect. For those that are still confused, this is the Tribonacci formula and works very similar to the Fibonacci DP (memoization) solution.
    1. Trib(n) = Trib(n-1)+Trib(n-2)+Trib(n-3) (for n>=3)
    2. seed the recursive function with base cases for n0=0, n1=1, n2=1.
    3. Use memoization to store results of previous numbers.
    The sequence goes something like 0,1,1,2,4,7,13,24,44,81….

    Reply
  9. If anyone is looking for a return type Long.

    public Long possibleWaysDyna(int n, Long [] dyn) {
    if (n 0) {
    return dyn[n];
    }
    dyn[n] = 1 + possibleWaysDyna(n – 1, dyn) + possibleWaysDyna(n – 2, dyn)
    ;
    return dyn[n];
    }

    Reply
  10. Solution is not correct.Your solution for 4 steps will return 8 but correct answer is 7.Below is correct one.

    public int countSteps(int n){
    if(n==0){
    return 1;
    }
    if(n<0){
    return 0;
    }
    return countSteps(n-1)+countSteps(n-2)+countSteps(n-3);
    }

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.