loading...

A note on Dynamic Programming

huytd profile image Huy Tr. ・1 min read

This is a quick note about Dynamic Programming from The Algorithm Design Manual book. I found it really helpful.

Why dynamic programming is so hard?

  • Until you understand dynamic programming, it seems like magic.
  • You must figure out the trick before you can use it.

The trick

  • Dynamic Programming is a technique for efficiently implementing a recursive algorithm by storing partial results.
  • The trick is: seeing whether the naive recursive algorithm computes the same subproblems over and over again.
  • If so, storing the answer for each subproblem in a table to lookup instead of recomputing.
  • Start with a recursive algorithm or definition. Only once we have a correct recursive algorithm, do we worry about speeding it up by using a result matrix.

The advice on how to learn

  • Dynamic programming is best learned by carefully studying examples until things start to click

Posted on by:

huytd profile

Huy Tr.

@huytd

Write code, drawing things

Discussion

markdown guide