Dynamic Programming – Stairs Climbing Puzzle

by · March 16, 2015

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Tags:

  • Pravinth

    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

    • tutorialhorizon

      Thanks, updated it.

  • Antonio M

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

    • tutorialhorizon

      Thanks Antonio for finding the miss, updated it

  • Harsh Shah

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

    • tutorialhorizon

      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.

      • Jing

        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?

      • Sneha Deshpande

        I need more clarification on why you have +1 at the end of the expression.

  • Soumitri Vadali

    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.

    • tutorialhorizon

      There are two approaches in dynamic programming, top-down and bottom-up. This is top-down (solve the smaller problem as needed and store result for future use, in bottom-up you break the problem in SMALLEST possible subproblem and store the result and keep solving it till you do not find the solution for the given problem. Please refer this link for more understanding.. http://algorithms.tutorialhorizon.com/introduction-to-dynamic-programming-fibonacci-series/

  • Ayushi

    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.

  • Hou GuoChen

    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.

    • vemurI krishna

      exactly . It’s true

  • Alex

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

  • Stretch

    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….

  • vaibhav shah

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

  • dheeraj singhal

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

Follow:

Select level

Beginner
Intermediate
Expert

Follow me on Twitter

%d bloggers like this: