Dynamic programming

dynamic programming의 세가지 조건

• simple subproblems : subproblems는 몇가지의 variables로 정의될 수 있다.
• Subproblem optimality : global optimum value는 optimal subproblems으로 정의될 수 있다.
• Subproblem overlap : subproblems은 독립적이지 않고 overlap한다. (그러므로 bottom-up으로 해결해야함)

Matrix Chain Multiplication

A= A0A1A2…An-1

matrix multiplication에서 최소의 matrix곱의 순서를 찾는 문제 => brute-force로 접근하면 오래 걸림.

전체 문제를 N0,n-1이라고 했을때 부분 문제인 Nij는 AiAi+1Ai+2….Aj까지의 곱에 사용되는 최소곱의 횟수.

0–1 Knapsack Problem

정해진 weight내에서 n 종류의 물건중에 선택하여 value를 최대화하는 문제.

남은 weight를 고려하지않으면 optimal-subproblem으로 정의 어려움.

1. Wk>w , 즉 k번째의 물건의 weight가 남은 weight보다 클때, 선택을 하지않기 때문에 k-1번째 물건까지의 value를 그대로 가져온다.

2. 그렇지 않으면 k번째 물건을 담는 방식과 담지 않는 방식중에서 큰 값을 고른다.

Longest Common Subsequence(LCS)

L[i,j] = 0 if i=-1 or j=-1

L[i,j] = L[i-1,j-1] +1 else if xi = yj

L[i,j] = max{L[i-1,j],L[i,j-1]} otherwise