Skip to main content
SpringerLink
Log in

Dynamic Programming

  • Living reference work entry
  • First Online:
Computer Vision

  • 273 Accesses

Synonyms

Dynamic optimization

Related Concepts

Inductive definition Recursion “Divide-and-conquer” algorithm

Definition

Dynamic programming is a paradigm used in algorithms for solving optimization problems. It relies on the construction of nested subproblems such that the solution of the main problem can be obtained from the solutions of the subproblems.

Background

The paradigm was introduced by the mathematician Richard Bellman in the 1940s and applied in control theory [1].

Theory

The applicability of the paradigm relies on the following two assumptions.

Optimal substructure means that a system of nested subproblems can be constructed in such a way that the solution of the main problem can be obtained from the solutions of these subproblems.

Overlapping subproblems mean that the smaller subproblems in the next level are only slightly smaller, and moreover the set of these subproblems is small as well. This distinguishes DP from “divide-and-conquer” methods.

The method starts by...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

References

  1. Bellman R (2003) Dynamic programming. Dover, Mineola

    MATH  Google Scholar 

  2. Denardo EV (2003) Dynamic programming: models and applications. Dover, Mineola

    MATH  Google Scholar 

  3. Sniedovich M (2010) Dynamic programming: foundations and principles. Taylor and Francis, Boca Raton

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Electrical Engineering, Department of Cybernetics, Czech Technical University Prague, Prague, Czech Republic

    Boris Flach

  2. Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University Prague, Prague, Czech Republic

    Vaclav Hlavac

Authors
  1. Boris Flach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vaclav Hlavac
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Boris Flach .

Section Editor information

  1. Okayama University, Okayama, Japan

    Kenichi Kanatani

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Flach, B., Hlavac, V. (2020). Dynamic Programming. In: Computer Vision. Springer, Cham. https://doi.org/10.1007/978-3-030-03243-2_690-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-03243-2_690-1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-03243-2

  • Online ISBN: 978-3-030-03243-2

  • eBook Packages: Springer Reference Computer SciencesReference Module Computer Science and Engineering

Publish with us

Policies and ethics

Search

Navigation