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

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