[이코테] DP

다이나믹 프로그래밍 (동적 계획법)

• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

• 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문에, 재귀함수는 가급적 사용하지 말 것.

코드

d = [0] * 100

def pibo(x):
	if (x == 1 or x == 2):
    	return 1
    if d[x] != 0:
    	return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))