페이지

2013년 11월 13일 수요일

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로 한계가 있으므로 문제를 보고 탐색 범위를 보고 더 효율적인 방법으로 풀면 된다.