Introduction to Dynamic Programming
Understand the concepts of dynamic programming and how you can identify the problems that can be solved using this approach.
We'll cover the following...
Welcome to the first lesson on dynamic programming. We will be learning how to identify the dynamic programming problems and also solve some of the most frequently asked problems in the interviews.
Those who cannot remember the past are condemned to repeat it.
Dynamic programming is all about remembering answers to the subproblems that you’ve already solved and not solving them again.
Where do we need dynamic programming?
If you are given a problem that can be broken down into smaller subproblems, which can be further be broken into smaller ones, and if you manage to find out that there are some overlapping subproblems, you’ve encountered a DP problem.
The core idea of dynamic programming is to avoid repeated work by remembering partial results.
Dynamic programming and Recursion
-
Dynamic programming is basically Recursion plus memoization.
-
Recursion allows you to express the value of a function in terms of other values of that function.
-
If you implement your function in a way that the recursive calls are done in advance and stored for easy access in the future, it will make your program faster.
This is what we call memorization: it is memorizing the results of some specific states, which can later be accessed to solve other subproblems.
The intuition behind dynamic programming is that we trade space for ...