CPU times: user 74 µs, sys: 0 ns, total: 74 µs Wall time: 78 µs 14930352

Staircase II

Suppose there is a staircase that you can climb in either 1 step, 2 steps, or 3 steps. In how many possible ways can you climb the staircase if the staircase has n steps? Write a recursive function to solve the problem.

Example:

n == 1 then answer = 1

n == 3 then answer = 4

The output is 4 because there are four ways we can climb the staircase:

%%time """ param: n - number of steps in the staircase Return number of possible ways in which you can climb the staircase """ # O(2^n), O(n) defstaircase(n): '''Hint''' # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps. # Recursive Step - Split the solution into base case if n > 3. if n == 1: # 1 return1 elif n == 2: # 1 - 1, 2 return2 elif n == 3: # 1 - 1 - 1, 1 - 2, 2 - 1, 3 return4 return staircase(n - 1) + staircase(n - 2) + staircase(n - 3)

staircase(30)

1 2 3

CPU times: user 3.93 s, sys: 24.3 ms, total: 3.95 s Wall time: 3.98 s 53798080

%%time """ param: n - number of steps in the staircase Return number of possible ways in which you can climb the staircase """ # O(n), O(n) @cache defstaircase(n): '''Hint''' # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps. # Recursive Step - Split the solution into base case if n > 3. if n == 1: # 1 return1 elif n == 2: # 1 - 1, 2 return2 elif n == 3: # 1 - 1 - 1, 1 - 2, 2 - 1, 3 return4 return staircase(n - 1) + staircase(n - 2) + staircase(n - 3)

staircase(30)

1 2

CPU times: user 42 µs, sys: 5 µs, total: 47 µs Wall time: 49.8 µs

%%time """ param: n - number of steps in the staircase Return number of possible ways in which you can climb the staircase """ # O(2^n), O(n) defstaircase(n): '''Hint''' # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps. # Recursive Step - Split the solution into base case if n > 3. def_staircase(i, n):# i current staircases if i > n: return0 elif i == n: return1 return _staircase(i + 1, n) + _staircase(i + 2, n) + _staircase(i + 3, n) return _staircase(0, n)

staircase(30)

1 2 3

CPU times: user 24.1 s, sys: 90.9 ms, total: 24.2 s Wall time: 24.4 s 53798080

%%time """ param: n - number of steps in the staircase Return number of possible ways in which you can climb the staircase """ # O(n), O(n) defstaircase(n): '''Hint''' # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps. # Recursive Step - Split the solution into base case if n > 3. @cache def_staircase(i, n):# i current staircases if i > n: return0 elif i == n: return1 return _staircase(i + 1, n) + _staircase(i + 2, n) + _staircase(i + 3, n) return _staircase(0, n)

staircase(30)

1 2 3

CPU times: user 59 µs, sys: 5 µs, total: 64 µs Wall time: 66 µs 53798080

Iteration

Python

1 2 3 4 5 6 7 8 9 10 11 12

%%time # Iteration # O(n), O(1) defstaircase(n): # F0, F1, F2, F3 # 1, 1, 2, F3 + F2 + F1 a, b, c = 1, 1, 2 for _ inrange(n): a, b, c = b, c, a + b + c return a

staircase(30)

1 2 3

CPU times: user 25 µs, sys: 1e+03 ns, total: 26 µs Wall time: 28.8 µs 53798080

Caching(manual)

Python

1 2 3 4 5 6 7 8 9 10 11

%%time classSolution: cache = {1: 1, 2: 2, 3: 4}

defstaircase(self, N: int) -> int: if N in self.cache: return self.cache[N] self.cache[N] = self.staircase(N - 1) + self.staircase(N - 2) + self.staircase(N - 3) return self.cache[N]

Solution().staircase(30)

1 2 3

CPU times: user 64 µs, sys: 1e+03 ns, total: 65 µs Wall time: 67.9 µs 53798080