######
**NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊**

*A child is running 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 run up the stairs.*

Hmm, this sounds a lot like a recursive algorithm 🤔To me the easiest way to think about it is to start backwards. Imagine that we have 5 steps and need to calculate all combinations of hops that can cover these 5 steps. We know that the child can hop either one step, 2 steps, or 3 steps at once - which means that she got to step 5 from either from step 4, or step 3, or step 2. In other words, if `n`

equals 5, then the number of different ways to get to n is a number of ways to get to `(n-1)`

+ ways to get to `(n-2)`

+ ways to get to `(n-3)`

. Let's call the function that would calculate the number of all possible ways to get to step x `getStaircaseCombinations(x)`

.

But how did the child get to step 4 (the `n-1`

from above)? She must have been either on step 3, step 2, or step 1 before, and you can observe the same pattern all over again. In other words, for each step `k`

we would need to return `getStaircaseCombinations(k-1) + getStaircaseCombinations(k-2) + getStaircaseCombinations(k-3)`

.

At which point do we stop? We know that the combination is correct if the sum of steps a child has made equals exactly to 5. We're going backwards, subtracting from 5 - which means that the correct combination should bring us to 0. So, when we're reaching 0 the combination must be valid and we should return 1. The alternative scenario is that we're ending up with a number less than 0: for instance, a child may have jumped to step 5 from step 2 (n-3) and to step 2 from step -1 (yet again, n-3). However, step -1 does not exist, a child would always start with step 0 - which means our combination does not work. So, for the cases resulting in a negative number we would return 0 and not count such combinations in.

This logic results in:

```
function getStaircaseCombinations(stairs) {
if (stairs < 0) { return 0; }
if (stairs === 0) { return 1; }
return (
getStaircaseCombinations(stairs - 1) +
getStaircaseCombinations(stairs - 2) +
getStaircaseCombinations(stairs - 3)
)
};
```

Finally, you can notice that in the code above we're calculating the same path several times. For instance, for `n=5`

you would need to calculate the number of step combinations for 'how to reach step 3' twice: for the case of `(n-2)`

and the case of `((n-1)–1)`

- and the bigger `n`

gets, the more double-work this code will be doing.

In order to avoid this, we can use memoization technique. The logic is as follows:

✔️start with the empty array of results

✔️if array of results doesn't contain yet the number of combinations for x (and only then!), calculate it and store it in the array as results[x]

✔️return the number of combinations for x stored in the array

The slightly adjusted code that allows for memoization will look like:

```
function getStaircaseCombinations(stairs) {
let combinations = [];
function calculateCombinations(n) {
if (n < 0) { return 0; }
if (n === 0) { return 1; }
if (combinations[n] === undefined) {
combinations[n] =
calculateCombinations(n - 1) +
calculateCombinations(n - 2) +
calculateCombinations(n - 3);
}
return combinations[n];
};
calculateCombinations(stairs);
return combinations[stairs];
}
```

## Discussion (1)

Pretty sure this can be done iteratively in O(1) space, since you actually only need to remember the previous three steps.