Dynamic Programming is method of solving complex problems by breaking them down into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems.
It is a powerful design technique that can be used to solve problems of computational nature. And it is typically applied to optimization problems.
Keys of Dynamic Programming:
1. Optimal substructure
An optimal solution to a problem (instance) contains optimal solutions to subproblems.
2. Overlapping subproblems
A recursive solution contains a “small” number of distinct subproblems repeated many times.
3. Bottom Up Fashion
Computing the solution in a bottom-up fashion to solve the problem.
It is a powerful design technique that can be used to solve problems of computational nature. And it is typically applied to optimization problems.
Keys of Dynamic Programming:
1. Optimal substructure
An optimal solution to a problem (instance) contains optimal solutions to subproblems.
2. Overlapping subproblems
A recursive solution contains a “small” number of distinct subproblems repeated many times.
3. Bottom Up Fashion
Computing the solution in a bottom-up fashion to solve the problem.
Areas:
- Bio-informatics
- Control theory
- Information theory
- Operations research
- Computer science: theory, graphics, AI, systems
Some famous dynamic programming algorithms:
- Unix diff for comparing two files
- Viterbi for hidden Markov models
- Smith-Waterman for sequence alignment
- Bellman-Ford for shortest path routing in networks
- Cocke-Kasami-Younger for parsing context free grammars
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.