# Climbing Stairs

DP

## # 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].

This problem is then equivalent to finding $n$-th fibonacci number.

### # Recursive DP w/ Memoization

memo corresponds to Fibonacci series: $1, 1, 2, 3, 5, 8, 13, 21, \cdots$

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 = [0 for _ in range(n+1)]
memo[0] = memo[1] = 1
return cs(n, memo)

1
2
3
4
5
6
7
8
9
10
11

### # Iterative DP w/ Memoization

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]

1
2
3
4
5
6
7
8

### # 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 $n$-th 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

1
2
3
4
5
6

### # Matrix Multiplication

As $F_{k+1} = F_{k} + F_{k-1}$, we can deduce the state transition between $F_{k}$, $F_{k-1}$ and $F_{k+1}$, $F_{k}$:

$\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix} \begin{bmatrix}F_{k}\\F_{k-1}\end{bmatrix} = \begin{bmatrix}F_{k} + F_{k-1}\\F_{k}\end{bmatrix} = \begin{bmatrix}F_{k+1}\\F_{k}\end{bmatrix}$

so we can use matrix multiplication to calculate the $n$-th Fibonacci number in log time:

$\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^n \begin{bmatrix}F_1\\F_0\end{bmatrix} = \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^n \begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}$

Complexity

time: $O(\log n)$
space: $O(1)$

def climbStairs(self, n: int) -> int:
def pow(a:List[List[int]], n: int) -> int:
"""Return matrix a to the n"""
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]]:
"""Return the multiplied matrix of a and b."""
c = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
return c

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

### # Golden 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)$

def climbStairs(self, n: int) -> int:
sqrt5 = math.sqrt(5)
fib_n = pow((1+sqrt5)/2, n+1) - pow((1-sqrt5)/2, n+1)
return int(fib_n/sqrt5)

1
2
3
4