Dynamic Programming - 기초

https://youtu.be/eJC2oetXaNk?si=n6ZFPnv56clCkA8f

코드없는 프로그래밍님의 영상이 가장 이해하기 좋았다.

 

<DP가 성립되기 위해서>

- Problem이 Sub Problem으로 쪼개질 때

- Sub Problem의 solution으로 Problem의 solution을 구할 수 있을 때

- 이런 Sub Problem들이 겹칠 때

 

fib_array=[0,1]

def fib_td(n): #Top-down
    if n<len(fib_array):
        return fib_array[n]
    else:
        fib=fib_td(n-1)+fib_td(n-2)
        fib_array.append(fib)
        return fib

하지만 Top-Down 방식은 recursion depth exceeded 에러가 발생할 수도 있음.

 

def fib_dp(n): #Bottom-up
    fib_array=[0,1]

    for i in range(2,n+1):
        num=fib_array[i-1]+fib_array[i-2]
        fib_array.append(num)
    return fib_array[n]

이러한 Bottom-up의 time complexity는 O(n)

space complexity는 O(n)에서 이전 값들은 지워도 되므로 O(1)까지로 줄어듦.

 

 

DP 너무 어렵다....