Dynamic Programming - intro

dynamic programming은
- careful brute force
- recursion + re-use
- shortest path in DAG
라고 볼 수 있다.


5 easy steeps to DP :

1. define subproblems
2. guess
1. guessing which subproblem to use to solve bigger problem
2. add more problems to guess/remember more
3. recurrence
4. recurse + memorize (acyclic인지 확인 필요)
   or bottom-up table (topological order를보고 bottom-up일지 top-down일지를 결정)
5. original problem

subproblem for strings/sequences 는 셋중 하나, 요 세개는 많이 쓰는 애들이니까 DP를 풀때 제일 먼저 생각해봐야 할 것들.

- suffix[i:]
- prefix[:i]
- substring[i:j]

이 교수님 강의 넘 맘에 든다. 귀에 쏙쏙. 4편까지 있음. 

씨리즈로 몇가지 문제를 풀어볼 생각이다.
DP 문제는 table 혹은 recursive 방식으로 모두 풀수 있다. recursive방식은 간단한 반면 탐색범위가 커지면 stack overflow로 한계가 있으므로 문제를 보고 탐색 범위를 보고 더 효율적인 방법으로 풀면 된다.

• Parenthesization
• Edit distance
• Knapsack
• Travelling Salesman problem