Common characterstics in dynamic programming

Dynamic Programming is an algorithm design technique for optimization problems: often minimizing or maximizing.

• Like divide and conquer, DP solves problems by combining solutions to subproblems.

• Unlike divide and conquer, subproblems are not independent.

Subproblems may share subsubproblems,
However, solution to one subproblem may not affect the solutions to other subproblems of the same problem. (More on this later.)

• DP reduces computation by:

Solving subproblems in a bottom-up fashion.
Storing solution to a subproblem the first time it is solved.
Looking up the solution when subproblem is encountered again.

• Key: determine structure of optimal solutions

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!