# Climbing Stairs ## # Solution

First we need to realize that "each time you can climb 1 or 2 steps" means the result is the sum of ways of the previous two steps.

Brute-force approach would be to recurse by reducing cs[n] to cs[n-1] + cs[n-2].

We will just start from the memoized recursion.

### # Recursion w/ Memoization

This is DP, the recursive version.

We could use recursion w/ the memoized array to trade time.

memo corresponds to Fibonacci series: 1, 1, 2, 3, 5, 8, 13, 21, ...

Complexity:

• Time: $O(n)$
• Space: $O(n)$
def climbStairs(self, n: int) -> int:

def cs(i: int, memo) -> int:
if (memo[i]>0): return memo[i]
else:
memo[i] = cs(i-1, memo) + cs(i-2, memo)
return memo[i]

memo =  * (n+1)
memo = memo = 1
return cs(n, memo)


### # Iteration & Build Up Array

This is DP, the iterative version.

Complexity:

• Time: $O(n)$
• Space: $O(n)$

Initialize arr to calculate current value based on the sum of previous two, stepwise towards n.

def climbStairs(self, n: int) -> int:
# use an int array to store previous steps
arr = []
arr.append(1)
arr.append(1)
for i in range(2,n+1):
arr.append(arr[i-1] + arr[i-2])

return arr[n]


### # Fibonacci Number

Complexity:

• Time: $O(n)$
• Space: $O(1)$

Then we realize we don't need any values except the previous two, so just keep a and b.

This is basically calculating the nth Fibonacci number.

def climbStairs(self, n: int) -> int:
if (n==1): return 1
a, b = 1, 1
for i in range(2,n):
a, b = b, a+b
return a+b


### # Matrix Multiplication

Note how to initialize a Python m $\times$ n matrix: [[0 for i in range(m)] for j in range(n)].

IMPT:

1. Should not do [*m]*n since * is shallow, not deep, copy
2. Exponentials should remind us of $\log$ runtime

Complexity:

• Time: $O(\log n)$
• Space: $O(1)$
def climbStairs(self, n: int) -> int:
def pow(a:List[List[int]], n: int) -> int:
ret = [[1, 0], [0, 1]]
while (n > 0):
if ((n & 1) == 1):
ret = multiply(ret, a)
n >>= 1
a = multiply(a, a)
return ret

def multiply(a:List[List[int]], b:List[List[int]]) -> List[List[int]]:
c = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
c[i][j] = a[i] * b[j] + a[i] * b[j]
return c

A = [[1,1], [1,0]]
return pow(A,n)


### # Gold Ratio

Using Fibonacci formula involving golden ratio is not recommended as the math formula is hard to remember or deduce.

$fib_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$

Then take the int part of this floating number.

Complexity:

• time: $O(\log n)$ due to pow method
• space: $O(1)$

Code is omitted.

Last Updated: 7/19/2020, 3:45:14 PM