I want to write a quick follow up to my last post on How to Solve the Staircase Problem with 5 Lines of JavaScript. It's a very elegant solution to the infamous staircase problem, however, as one commentor noted it's terribly inefficient to the order...
Markdown supported · ⌘↵ to post
You could also do away with recursion altogether by applying dynamic programming. Start with an array of 3 values [1,2,4] for the possibilities of the first 3 steps and then calculate the following positions as the sum of the previous 3 positions in the array. The value at N - 1 is the number of possibilities.
The order of the old implementation is not O(n^3) it's O(3^n) as you branch 3 times for each call, and you have total n different cases, so it's 3 * 3 * 3 * 3 ... n times which is 3^n.
Pardon me for rewriting in Python.
My code runs without recursion and at about the same speed.
def StairCaseMemo(N): memo = {} def stepsM(N): if N == 0: return 1 elif N<0: return 0 if N in memo.keys(): return memo[N] else: memo[N] = stepsM(N - 1) + stepsM(N - 2) + stepsM(N - 3); return memo[N]; print(stepsM(N)) def StairCaseMine(limit): # initial setup array = {} array[0] = 1 array[1] = array[2] = index = 0 while index < limit: count = array[index] array[index+1] += count array[index+2] += count array[index+3] = count index += 1 print(array[limit])Enjoy!