Dynamic Programming

  • Last Updated : 26 Sep, 2023

DSA for Beginners
Learn more about Dynamic Programming in DSA Self Paced Course
Practice Problems on Dynamic Programming
Top Quizzes on Dynamic Programming

What is Dynamic Programming?

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.


Basic Concepts:

  1. What is memoization? A Complete tutorial
  2. Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
  3. Tabulation vs Memoizatation
  4. Optimal Substructure Property
  5. Overlapping Subproblems Property
  6. How to solve a Dynamic Programming Problem ?

Advanced Concepts:

  1. Bitmasking and Dynamic Programming | Set 1
  2. Bitmasking and Dynamic Programming | Set-2 (TSP)
  3. Digit DP | Introduction
  4. Sum over Subsets | Dynamic Programming

Standard problems on Dynamic Programming:

Quick Links :

  1. Learn Data Structure and Algorithms | DSA Tutorial
  2. Top 20 Dynamic Programming Interview Questions
  3. ‘Practice Problems’ on Dynamic Programming
  4. ‘Quiz’ on Dynamic Programming

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.