May 6, 2018

[algorithm][DP] thinking steps


  1. Define subproblems : count number of subproblems
  2. Guess(part of solution)  (fib doesn't need to guess, it's specific)
  3. Relate subproblems solutions(with recursion) (想出其中的關聯)
  4. Recurse & memoize OR buttom up approach(for loop). (must be asyclic, DAG, thus can use toposort.)
  5. Solve original problem (確定真的解決原本的問題)

Supplement article: Tail call

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.