Dynamic programming

Dynamic programming is a method for efficiently solving a broad range of search and optimization problems which exhibit the characteristics of overlappling subproblems and optimal substructure. I’ll try to illustrate these characteristics through some simple examples and end with an exercise. Happy coding!

Contents

Common Characterstics of Dynamic programming
Overlapping Subproblems
Optimal Substructure
The Knapsack Problem
Everyday Dynamic Programming

Everyday Dynamic Programming

The above examples might make dynamic programming look like a technique which only applies to a narrow range of problems, but many algorithms from a wide range of fields use dynamic programming. Here's a very partial list.

1. The Needleman-Wunsch algorithm, used in bioinformatics.
2. The CYK algorithm which is used the theory of formal languages and natural language processing.
3. The Viterbi algorithm used in relation to hidden Markov models.
4. Finding the string-edit distance between two strings, useful in writing spellcheckers.
5. The D/L method used in the sport of cricket.

That's all for today. Cheers!