I'm looking at the following challenge:
Fibonacci is a young resident of the Italian city of Pisa. He spends a lot of time visiting the Leaning Tower of Pisa, one of the iconic buildings in the city, that is situated close to his home. During all his visits to the tower, he plays a strange game while climbing the marble steps of the tower.
The Game: Fibonacci likes to climb the steps either one at a time, two at a time or three at a time. This adds variety to the otherwise monotonous task of climbing. He wants to find the total number of ways in which he can climb n steps, assuming that the order of his individual steps matters. Your task is to help Fibonacci compute this number.
For example, if he wishes to climb three steps, the case of n=3, he could do it in four different ways: (1,1,1): do it in three moves, one step at a time (1,2): do it in two moves, first take a single step, then a double step (2,1): do it in two moves, first take a double step, then a single step (3): do it in just one move, directly leaping to the third step To take another example, if n=5, then some of the sequences could be: (1,3,1),(1,1,3),(3,1,1),(2,1,1,1),(1,2,1,1),(2,1,2) Each sequence is one of the ways of climbing five steps.
The point to note here is that each element of a sequence can only be 1, 2 or 3. Write a recursive function named steps that accepts a positive integer n as an argument. It should return the total number of ways in which Fibonacci can ascend n steps. Note that the order of his steps is important.
I assume that the logic would be the same as a simple combinatorics problem where we distribute n indistinguishable objects into n distinguishable boxes such that each box at max contains k objects and find the number of possible arrangements for each combination, hence the title. Is this the correct way to look at it, or am I taking the wrong approach?
This is a Tribonacci sequence, following sequence A000073, skipping the first two zeroes, so for 𝑛 starting at 0, the sequence is 1, 1, 2, 4, 7, 13, 24, ...etc.
A naive recursive function would look like this:
function steps(n) {
if (n < 2) return 1
if (n == 2) return 2
return steps(n-3) + steps(n-2) + steps(n-1)
}
If really implemented as a recursive function you'd better apply memoization to make sure it executes in linear time.
Note that such recursive implementation has a space complexity of O(𝑛). A more memory efficient way is to not implement it as a recursive function, but iteratively, which has a O(1) space complexity:
function steps(n) {
a = 0
b = 0
c = 1
while (n > 0) {
d = a + b + c
a = b
b = c
c = d
n = n - 1
}
return c
}
First, in the story of the staircase, let's call a step the part of the staircase, and a move the action you take to climb the stairs (in English the word "step" can be used for both, but that makes it quite confusing).
In the story, when you are 𝑛 steps away from the top (and 𝑛 > 2), you have three options for your next move: the move takes one step, two steps or three steps, reducing 𝑛 with the same amount. If for each of these options you know how many possibilities there are to continue further to the top, then you can just take the sum of those three counts and conclude how many possibilities there are when you are 𝑛 steps away from the top.
So we have this recurrence relation, where 𝑇𝑛 represents the number of possibilities when you are 𝑛 steps away from the top:
𝑇𝑛 = 𝑇𝑛−1 + 𝑇𝑛−2 + 𝑇𝑛−3
What remains is to determine the counts for when 𝑛 is small:
𝑇0 = 1
𝑇1 = 1
𝑇2 = 2
The first one, 𝑇0, may feel non-intuitive, but when you are 0 steps away from the top, you are already at the top, and no more moves are needed. Yet, you achieved the goal, so it counts as 1: there evidently is a way to reach the top -- by doing nothing.
With these specification of 𝑇, the recursive function follows naturally.