[python] 다이나믹 프로그래밍

- 중복 연산 줄임

1) 최적 부분 구조

2) 중복되는 부분 문제

- 두 조건 만족하면 사용 가능

 

예) 피보나치 수열

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

 

- 점화식 : 인접한 항들 사이의 관계식

 

# 피보나치 함수 (재귀 함수)

# 피보나치 함수(재귀함수)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

 

 

# 메모이제이션

- 탑다운, 하향식

- 메모했던 결과를 그대로 가져옴

- 캐싱 (값을 기록)

d = [0] * 100

# 피보나치 함수(재귀함수) - 탑다운 다이나믹 프로그래밍
def fibo(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))

 

 

# 보텀업

- 상향식

- 반복문

d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(반복문) - 보텀업 다이나믹 프로그래밍
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])