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

Dynamic Programming(DP) 란?

• optimization problem (최적의 답을 찾아야 하는 문제) 의 해결 전략 중 하나.
• 최종적인 답이 여러 개의 sub problem 들의 optimal 솔루션을 활용해서 구해질 수 있을 때 사용하는 방식.

DP 를 쓰기 위해 확인해야 할 조건

• optimal solution이 sub problems의 opitmal solution을 포함하는 구조여야 한다.
  • ex) f(n) = f(n-1) + f(n-2)
• sub problems 들은 서로 다른 sub problem solution에 영향을 줘선 안된다. (독립적이어야 한다)
• 동일한 sub problem 들을 여러 번 해결해야 해서 그 결과를 저장해 두고 재사용할 때 계산을 다시 할 필요 없이 값을 그대로 쓰기 좋은 구조여야 한다.

DP 의 두가지 접근 방식?

• Top-Down 방식
  recursion을 활용 + 이 과정의 function call 결과를 저장 -> memoization 기법을 활용하는 방식

  • 코드 예시)

    dp = []
    
    def climb(n):
    	if n in dp:
        	return memo[n]
        if n <= 2:
        	return n
        memo[n] = climb(n-1) + climb(n-2)
        return memo[n]

• Bottom-Up 방식
  iterative한 방식으로 작은 sub problem부터 시작해 최종 problem 까지의 결과를 차례대로 기록 -> tabulation 기법을 활용하는 방식

  • 코드 예시)

    
    dp = [0] * len(numbers)
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n+1):
    	dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]