DEV Community

Huy Tr.
Huy Tr.

Posted on

5

A note on Dynamic Programming

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

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more