# Triple Step

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.

## Link here to the repo to solve the problem

👉## 👌 Tips

Approach this from the top down. What is the very last hop the child made?

If we knew the number of paths to each of the steps before step 100, could we compute the number of steps to 1OO?

We can compute the number of steps to 100 by the number of steps to 99, 98, and 97. This corresponds to the child hopping 1, 2, or 3 steps at the end. Do we add those or multiply them? That is: Is it f(100) = f(99) + f(98) + f(97) or f(100) = f(99) * f(98) * f(97)?

We multiply the values when it's "we do this then this" We add them when it's "we do this or this"

What is the runtime of this method? Think carefully. Can you optimize it?

Try memoization as a way to optimize an inefficient recursive program.

## 👊 Solution

In order to solve this question, we need to think about what is the last step we need to do prior finishing the hops. The last hop we did was either n - 1, n - 2 or n - 3. Let's try to find a way in which we can relate it to some sub-problems.

If we think about all the paths to the nth step, we could just build them off the paths to the three previous steps. We can get to that Nth step by any of the following steps:

- going to n - 1 by hopping 1 step
- going to n - 2 by hopping 2 steps
- going to n - 3 by hopping 3 steps

Therefore, we just need to add the number of these paths together.

```
int countWays(int n) {
if (n < 0) return 0;
if (n == 0) return 1;
return countWays(n - 1) + countWays(n - 2) + countWays(n - 3);
}
```

Following a similar approach as the Fibonacci example, this would take O(3^N), where 3 is the amount of branches we are recursing each time, and N is the depth.

## 👊 Solution Memoization

If we draw the example, in a very similar fashion as in Fibonacci, you'll be able to tell that a lot of computations get repeated. For instance if we have the number 5, there will be many paths that in order to reach 5 will be combinations like: {3, 2}, {2, 2, 1}, etc. We can definitely store this values in a cache and avoid pre-computing them.

```
int countWays(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1); // we need to make sure the array does not have 0 as its default, as 0 is a valid value for our base case.
return countWays(n, memo);
}
int countWays(int n, int[] memo) {
if (n < 0) {
return 0;
}
else if (n == 0) return 1;
else if (memo[n] > -1) return memo[n];
else {
memo[n] = countWays(n - 1, memo) + countWays(n - 2, memo) + countWays(n - 3, memo);
return memo[n];
}
}
```

It is important to notice, that after a certain point, the integer will overflow (in this case 37 would do it).

Integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower than the minimum representable value.

It's important to be aware that some numbers will be hard to calculate as a normal integer, and some other data types might need to be used.

*Question borrowed from “Cracking the coding interview”*