Dynamic Programming - Algorithms That Use Dynamic Programming

Algorithms That Use Dynamic Programming

• Recurrent solutions to lattice models for protein-DNA binding
• Backward induction as a solution method for finite-horizon discrete-time dynamic optimization problems
• Method of undetermined coefficients can be used to solve the Bellman equation in infinite-horizon, discrete-time, discounted, time-invariant dynamic optimization problems
• Many string algorithms including longest common subsequence, longest increasing subsequence, longest common substring, Levenshtein distance (edit distance).
• Many algorithmic problems on graphs can be solved efficiently for graphs of bounded treewidth or bounded clique-width by using dynamic programming on a tree decomposition of the graph.
• The Cocke–Younger–Kasami (CYK) algorithm which determines whether and how a given string can be generated by a given context-free grammar
• Knuth's word wrapping algorithm that minimizes raggedness when word wrapping text
• The use of transposition tables and refutation tables in computer chess
• The Viterbi algorithm (used for hidden Markov models)
• The Earley algorithm (a type of chart parser)
• The Needleman–Wunsch and other algorithms used in bioinformatics, including sequence alignment, structural alignment, RNA structure prediction.
• Floyd's all-pairs shortest path algorithm
• Optimizing the order for chain matrix multiplication
• Pseudo-polynomial time algorithms for the subset sum and knapsack and partition problems
• The dynamic time warping algorithm for computing the global distance between two time series
• The Selinger (a.k.a. System R) algorithm for relational database query optimization
• De Boor algorithm for evaluating B-spline curves
• Duckworth–Lewis method for resolving the problem when games of cricket are interrupted
• The Value Iteration method for solving Markov decision processes
• Some graphic image edge following selection methods such as the "magnet" selection tool in Photoshop
• Some methods for solving interval scheduling problems
• Some methods for solving word wrap problems
• Some methods for solving the travelling salesman problem, either exactly (in exponential time) or approximately (e.g. via the bitonic tour)
• Recursive least squares method
• Beat tracking in music information retrieval.
• Adaptive-critic training strategy for artificial neural networks
• Stereo algorithms for solving the correspondence problem used in stereo vision.
• Seam carving (content aware image resizing)
• The Bellman–Ford algorithm for finding the shortest distance in a graph.
• Some approximate solution methods for the linear search problem.
• Kadane's algorithm for the maximum subarray problem.