DP DP DP DP DP DP

Dynamic programming is applicable when the subproblems are independent!!

• Characterize the sutructure of an optimal solution
• Recursively define the vaule of an optimal solution
• Compute the value of an optimal solution in a bottom-up fashion
• Construct an optimal solution from computed information

In order for dynamic programming to apply, the problem must have

1. Optimal substructure

   • 전체 최적해는 부분문제들의 최적해들로 이루어진다.
   • 어떤 문제가 optimal substructure를 가지면, 그 문제는 동적 계획법을 적용할 수 있는 강한 신호이다.
   • 동적 계획법에서는 부분문제들의 최적해를 이용하여 전체 문제의 최적해를 구성한다.
   • 결과적으로, 우리가 고려하는 부분문제의 범위가 최적해를 구성하는 데 사용되는 부분문제들을 포함하도록 보장해야 한다.
     • 최적해를 구성하는 데 필요한 ‘모든 종류의 부분문제 상태’가 정의 안에 포함되어야 한다.

2. Overlapping subproblems

   • When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has "overlapping subproblems".