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.