1. Recursive Call

def f(n):
	if n == 0 : return 0
	if n == 1 : return 1
	
	return f(n-1) + f(n-2)
	
	# 마지막 recursive call 두 번으로 인해 다음과 같은 시간복잡도
	# Time : O(2^n) 

보통 O(2^N) 으로 인해 위 방법은 잘 사용치 않음 :-)

2. Top-Down DP (Memoization)

def fib(n):
	memo = {0:0, 1:1}
	
	def f(n):
		if n in memo:
			return memo[n]
			
		memo[n] = f(n-1) + f(n-2)
		return memo[n]
		
	return f(n)
	
	# Time : O(n)

When to use ??

• To compute only until find the answer
• To use recursion

Use it when you only need to compute the solution for a small subset of possible inputs (i.e., not all values up to n).

It's particularly useful when the problem involves recursion with overlapping subproblems.

3. Bottom-Up DP (Tabulation)

def fib(n):
	dp = [0,1]
	
	for i in range(2,n+1):
		new = dp[i-2] + dp[i-1]
		dp.append(new)
		
	return dp[n]
	
	# Time : O(n)

When to use ??

• To avoid recursion
• For more space efficient

Use it when you want to avoid recursion overhead or when recursion depth is a concern.

It's more space-efficient because it doesn't involve the overhead of recursive function calls and maintains only the necessary state.

4. Bottom-Up No-Memory DP

def fib(n):
	if n < 2: return n
	
	prev = 0
	cur = 1
	for i in range(2,n+1):
		prev = cur
		cur = cur + prev
		
	return cur
	
	# Time : O(n)
	# 위 두 가지 방식보다 변수를 덜 쓴다.
	# 따라서 상대적으로 공간복잡도를 개선할 수 있다.

When to use ?

• Only when the problem is sipmle
• For more memory efficient

하지만 위 방법은 복잡한 솔루션이 필요한 문제에 대해서는 유용하지 못 하다.

따라서 Top-Down / Bottom-Up 을 유용하게 사용하는 게 효율적일 것이다.

Reference

https://www.youtube.com/shorts/uUjFL0C-vY0