Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Stairs Climbing Puzzle

Objec­tive: A child is climb­ing up a stair­case with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Imple­ment a method to count how many pos­si­ble ways the child can jump up the stairs.

Exam­ple:

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 num­ber of ways to com­plete n-1 steps +1.
  • Sim­i­larly if child take 2 steps then find the num­ber of ways to com­plete n-2 steps +1.
  • If child take 3 step then find the num­ber of ways to com­plete n-3 steps +1.
  • 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.

Using Recur­sion:


If we solve this prob­lem using recur­sion then all the sub-problems will be cal­cu­lated repeatedly.

Using Dynamic Pro­gram­ming:

  • We will solve it Top-Down approach.
  • We need to store the solu­tions for the sub prob­lems in an array.

DP Code:

Out­put:

4

You may also like...

  • 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

    • tuto­ri­al­hori­zon

      Thanks, updated it.

  • Anto­nio M

    you are not using the dyn array to store any­thing. here is the solution.

    pub­lic 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];
    }

    • tuto­ri­al­hori­zon

      Thanks Anto­nio for find­ing the miss, updated it

  • Harsh Shah

    what is the +1 for ? shouldn’t the recur­rence rela­tion be dyn[n] = poosibleWaysDyna(n — 1, dyn) + poosibleWaysDyna(n — 2, dyn) + poosibleWaysDyna(n — 3, dyn);

    • tuto­ri­al­hori­zon

      Hi Harsh,

      +1 is for the step we are taken already. If you look at the recur­rence rela­tion, we are solv­ing 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 solv­ing the remain­ing steps recur­sively). 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 cor­re­spond­ing to poosibleWaysDyna(n — 1, dyn),poosibleWaysDyna(n — 2, dyn) and poosibleWaysDyna(n — 3, dyn) respec­tively. So the last step can have 3 types. Why do you con­sider 3 kinds of last step as only 1?

      • Sneha Desh­pande

        I need more clar­i­fi­ca­tion on why you have +1 at the end of the expression.

  • Soumitri Vadali

    how is this dynamic at all? You are still recur­sively call­ing dif­fer­ent func­tions. The whole idea is to save spae and time and that is not being done here in either approach.

    • tuto­ri­al­hori­zon

      There are two approaches in dynamic pro­gram­ming, top-down and bottom-up. This is top-down (solve the smaller prob­lem as needed and store result for future use, in bottom-up you break the prob­lem in SMALLEST pos­si­ble sub­prob­lem and store the result and keep solv­ing it till you do not find the solu­tion for the given prob­lem. Please refer this link for more under­stand­ing.. http://algorithms.tutorialhorizon.com/introduction-to-dynamic-programming-fibonacci-series/

  • Ayushi

    This gives incor­rect out­put for n = 4.
    There are only 7 pos­si­ble ways for 4 stairs: 1111,112,121,211,13,31,22 but your solu­tion gives the value 8.

  • Hou GuoChen

    You do not +1 to the result. The recur­rence rela­tion is just ways(n-3) + ways(n-2) + ways(n-1).
    In your approach, you are con­fus­ing the num­ber of ways vs the addi­tional step taken to reach N. Tak­ing the addi­tional step con­tributes to EACH of the step com­bi­na­tion in each way, but does NOT con­tribute to the total num­ber of ways it takes.

    exam­ple:
    First, let’s define the base cases for N=1,2,3 respec­tively.
    Note: we are using alpha­bets to uniquely iden­tify the actual combinations.

    If N = 1, there’s 1 way to reach N.
    the actual com­bi­na­tions are:
    a. 1

    if N=2, there’s 2 ways to reach N.
    the actual com­bi­na­tions are:
    b. 1,1
    c. 2

    if N=3, there’s 4 ways to reach N.
    the actual com­bi­na­tions 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 brack­ets in com­bi­na­tions below means the actual com­bi­na­tions we took from the case indi­cated 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 addi­tional step (either 1,2,3) is the actual step required to take to com­plete each way to attain the new N and NOT an addi­tional way.

    • vemurI krishna

      exactly . It’s true

  • Alex

    pub­lic sta­tic 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 pre­vi­ous posters pointed out the for­mula used in this page is incor­rect. For those that are still con­fused, this is the Tri­bonacci for­mula and works very sim­i­lar to the Fibonacci DP (mem­o­iza­tion) solu­tion.
    1. Trib(n) = Trib(n-1)+Trib(n-2)+Trib(n-3) (for n>=3)
    2. seed the recur­sive func­tion with base cases for n0=0, n1=1, n2=1.
    3. Use mem­o­iza­tion to store results of pre­vi­ous num­bers.
    The sequence goes some­thing like 0,1,1,2,4,7,13,24,44,81.…

  • vaib­hav shah

    If any­one is look­ing for a return type Long.

    pub­lic 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];
    }