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.
- What is memoization? A Complete tutorial
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
- Tabulation vs Memoizatation
- Optimal Substructure Property
- Overlapping Subproblems Property
- How to solve a Dynamic Programming Problem ?
- Bitmasking and Dynamic Programming | Set 1
- Bitmasking and Dynamic Programming | Set-2 (TSP)
- Digit DP | Introduction
- Sum over Subsets | Dynamic Programming
Standard problems on Dynamic Programming:
Quick Links :
- Learn Data Structure and Algorithms | DSA Tutorial
- Top 20 Dynamic Programming Interview Questions
- ‘Practice Problems’ on Dynamic Programming
- ‘Quiz’ on Dynamic Programming
If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to email@example.com. 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.