If you are happy and you know it, jump up high!

Question

You are standing on step 0 of a staircase. Your goal is to reach the step n. At each step i, you have three choices: hop to next step i+1, i+2 or i+3 Give an algorithm to count the number of possible paths to reach n.

Please provide the Notation, optimality, recurrence, and algorithm.

Answer 1

This is a modification of fibonacci problem

Notation:

Let us consider S[i] be the number of possible paths from step 0 till n where one can hop by +1 or +2 or +3 only

Recurrence:

S[i] = S[i-1] + S[i-2] + S[i-3]

Algorithm:

S[1] = 1 //One possible way to go from 0 till 1

S[2] = 2 // 0-1-2 or 0-2

S[3] =4 //0-1-2-3 or 0-1-3 or 0-2-3 or 0-3

for(i=4;i<=n;i++)

{

S[i] = S[i-1] + S[i-2] + S[i-3];

}

return S[n];

Time Complexity:

Since there is single loop it is O(n)

Answer 2

A simple retreat, you only have three actions to reach the final state