DP(Dynamic Programming) 동적계획법

DP(Dynamic Programming)

f(n)을 1부터 n까지의 곱을 구하는 함수라고 정의를 내리면
f(n) = f(n-1)*n (n>1) : 점화식
f(1) = 1 : 초기조건

첫번째방법으로 for loop를 통하여 1부터 n번까지의 곱을 구할 수 있습니다.
 f(i-1)의 값을 알고있다는 전제하에 f(1)을 초기조건으로 설정하면
f(n)의 값을 구하는것이 가능해집니다

f[1]=1
for i in range(2,n+1):
    f[i] = f[i-1]*i
print(f[n])

두번째 방법으로는 재귀함수를 이용하는 것입니다. 백트래킹과 유사하게 종료조건을 초기조건으로 넣어주고
else 부분을 점화식으로 작성해주면 됩니다.

def f(n):
    if n==1:
        return 1
    else:
        f[n] = f[n-1]*n
print(f(n))

--------------------------------------------

동적계획법인 DP는 이렇게 for문을 이용하거나 재귀함수를 이용하여 문제를 해결할 수 잇습니다.

for문을 이용하여 순서대로 배열에 값을 채워나가는 방식을 (Bottom-up) tabulation이라하고
재귀적인 방법을 이용하여 값을 기록하고 그 기록한 값을 참조하여 중복연산을 피하는 방법을 (Top-down)memoization이라고 부릅니다.

memoization의 경우에는 높은수에서 낮은수로 가기때문에 탑다운방식(Top-down Approach),
tabulation같은 경우에는 아래값에서 높은값을 채워나가기 때문에 바텀업방식(Bottom-up)라고 부릅니다.

이론적으로는 시간복잡도는 두 방식모두 크게보면 동일하나 탑다운 방식일경우 재귀를 실행할때마다 재귀의 깊이가 깊어져
함수처리에 추가적인 시간이 약간 더 붙어 바텀업방식이 약간 더 빠릅니다.

*다이나믹 프로그래밍 문제해결을 위한 순서도
1. DP의 정의. D(i)가 무엇이 될지를 정의하기.
2. 점화식 세우기 : 큰 상태를 만들기위해 이전상태(작은건) 어떨까 라는 사고과정
3. 초기값(초기설정)
4. 빠진조건이 있는지 꼼꼼히 확인하기.

위 코드의 경우에는 한칸 앞, 피보나치수열의 f(n)의 값을 구하는 경우에는 위의 그림과같이 2칸의 경우를 고려해주는 점화식을 구성토록한다.