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

중간 계산값을 다른 변수에 미리 변수에 저장해놓는 형태의 방법.

동적 계획법을 설명하면 항상 같이 나오는 피보나치 수열 관련해서..

읽어보기 : http://xaya_epica.blog.me/220061394723

http://cafe.naver.com/ehclub/book5079308/1748

요약 : 재귀함수로 피보나치를 구현하면 뒤로 갈수록 느려진다. 이유는 앞의 수를 계산할때도 난 이미 값을 알지만 프로그래밍적으로는 재귀하므로 계속해서 함수 속으로 들어가기 때문.

동적 계획법을 이용하면 이미 아는 값은 변수에 따로 넣어 줌으로서 이러한 재귀를 피할 수 있다.

아래 코드는 재귀와 동적 계획법 차이 예제이다. 따로따로 실행시켜보자.

# -*- encoding: cp949 -*-
def fibonacci(i): #재귀를 이용
    if i<=1:
        return 1
    else:
        return fibonacci(i-1)+fibonacci(i-2)

for i in range(100):
    print fibonacci(i)

######################################

fibo = [0 for i in range(100)] #동적 계획법 이용
fibo[0] = 1
fibo[1] = 1
for i in range(2,100):
    fibo[i] = fibo[i-1] + fibo[i-2]
    print fibo[i]

아래는 또다른 좋은 예제이다. 링크의 문제를 풀어보자. 이것도 완전 다 찾아가는 탐색으로 구현이 가능하고, 동적 프로그래밍으로 함수호출을 줄일 수 있다.

https://algospot.com/judge/problem/read/JUMPGAME

아래 사이트에 좋은 답변 예시가 있다.

http://twodude.com/220698755334

이 사이트의 답을 파이썬으로 구현한 예시이다.(저 사이트의 코드를 그대로 가져왔다.)

저기에도 설명되어있지만 호출 차이가 어마어마하게 차이난다.(272271번과 199번.)

예시가 많고 많이 나오는만큼 알아둬야할것같다.

# -*- encoding: cp949 -*-
j1 = 0
j2 = 0
def jump(F,n,y,x):
    global j1
    j1 += 1
    if y>=n or x>=n:
        return 0
    elif y==n-1 and x==n-1:
        return 1
    else:
        return jump(F,n,y+F[y][x],x) + jump(F,n,y,x+F[y][x])
def jump2(F,M,n,y,x):
    global j2
    j2 += 1
    if y>=n or x>=n:
        return 0
    elif y==n-1 and x==n-1:
        return 1
    else:
        if M[y][x] != -1:
            return M[y][x]
        M[y][x] = jump2(F,M,n,y+F[y][x],x) + jump2(F,M,n,y,x+F[y][x])
        return M[y][x]

def main():
    C = int(raw_input())
    n = range(C)
    for i in range(C):
        n[i] = int(raw_input())
        F = [[] for j in range(n[i])]
        for j in range(n[i]):
            F[j] = map(int,raw_input().split())
        M = [[-1 for k in range(len(F))] for j in range(len(F))]
        print u'도달가능? =',jump(F,n[i],0,0) #1이 리턴되면 도달가능, 0이 리턴되면 도달 불가능하다는 소리이다.
        print u'도달가능? =',jump2(F,M,n[i],0,0)
        print j1 #완전탐색으로 구현했을경우의 탐색횟수,
        print j2 #동적계획법으로 구현했을경우의 탐색횟수이다.
if __name__=='__main__':
    main()

추가 읽어보기.

http://andromeda-express.com/dp/#slide1

http://secom.hanbat.ac.kr/or/ch10/right04.html

http://omnis.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C-2%ED%9A%8C