# What is dynamic programming?

@article{Eddy2004WhatID, title={What is dynamic programming?}, author={Sean R. Eddy}, journal={Nature Biotechnology}, year={2004}, volume={22}, pages={909-910} }

Sequence alignment methods often use something called a 'dynamic programming' algorithm. What is dynamic programming and how does it work?

#### Supplemental Presentations

#### Paper Mentions

#### 6,825 Citations

Algorithms, analysis and software for the global optimization of two-stage stochastic programs

- Computer Science
- 2018

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Chemical Engineering, 2018.

A DYNAMIC PROGRAMMING SOLUTION OF THE JEEP PROBLEM

- 2010

The jeep problem is solved by dynamic programming.

Recursion Schemes for Dynamic Programming

- Mathematics, Computer Science
- MPC
- 2006

A new recursion combinator, dynamorphism, is presented, which captures the dynamic programming recursion pattern with memoization and identifies some simple conditions when functions defined by structured general recursion can be redefined as a dynamorphisms. Expand

A Mathematical Optimization Problem in Bioinformatics

- Mathematics
- 2008

Abstract This article describes the sequence alignment problem in bioinformatics. Through examples, we formulate sequence alignment as an optimization problem and show how to compute the optimal… Expand

Abstract Dynamic Programming

- Computer Science
- 2013

Dynamic Programming Dimitri P. Bertsekas Massachusetts Institute of Technology WWW site for book information and orders http://www.athenasc.com Athena Scientific, Belmont, Massachusetts

A dynamic programming approach to achieving an optimal end-state along a serial production line

- Engineering
- IEEE Engineering Management Review
- 2015

This publication contains reprint articles for which IEEE does not hold copyright. Full text is not available on IEEE Xplore for these articles.

A Logic-based Approach to Dynamic Programming

- 2004

We present a first-order value iteration algorithm that addresses the scalability problem of classical dynamic programming techniques bylogically partitioning the state space. An MDP is represented… Expand

An improving dynamic programming algorithm to solve the shortest path problem with time windows

- Computer Science, Mathematics
- Electron. Notes Discret. Math.
- 2010

An efficient way of reducing the number of labels saved and dominance computing time is proposed and validated by experiments on shortest path problem with time windows instances. Expand

Practical Protein Sequence Alignment With Algebraic Dynamic Programming

- Computer Science
- 2003

This work examines several heuristic techniques for filtering unlikely candidates and locating specific sites for local alignment, and discusses plans for developing domain specific languages for alignment problems, which use heuristics to restrict the range of alignment. Expand

Industrial Applications of Probabilistic Model Checking- A Model-based Approach for Embedded Networked Systems and Concurrent Data Structures -

- Computer Science
- 2017

xi Zusammenfassung xiii

#### References

SHOWING 1-4 OF 4 REFERENCES

Eye of the hurricane : an autobiography

- Engineering
- 1984

This is a very frank and detailed account by a leading and very active mathematician of the past decades whose contributions have had an important impact in those fields where mathematics is now an… Expand

Traveling Salesman Problem Sariel (UIUC) New CS473 81 Fall

- Traveling Salesman Problem Sariel (UIUC) New CS473 81 Fall
- 1981

The complexity of this algorithm is O(N 2 ), where N = S.length

- The complexity of this algorithm is O(N 2 ), where N = S.length

Traveling Salesman Problem Problem (TSP) Input: A graph G = (V, E) with non-negative edge costs/lengths

- Traveling Salesman Problem Problem (TSP) Input: A graph G = (V, E) with non-negative edge costs/lengths