Welcome Learners, in this post Dynamic Programming (DP) you will know briefly what is dynamic programming. You will also know about where to use it. You can refer my previous posts Two Pointers Technique/Approach and Greedy Algorithm if needed.
Introduction to Dynamic Programming (DP)
Dynamic programming a wonderful and simple technique used for developing optimized solutions for the problem. It is a bit confusing to understand at the beginning. But if you understand it clearly, it is a piece of cake for you. Dynamic programming is a design technique which uses the result of the subproblems. By using this result it computes the solution for the main problem. In divide and conquer the subproblems are different. You will merge the result of subproblems to get final result. But in dynamic programming you use the result of subproblem and compute for the bigger problem.
Where you should use Dp
Dynamic programming is used when you have independent subproblems. It computes the result of smaller subproblem. And it uses it later for bigger problems.
DP characteristics
- identify whether the problem consists of independent subproblems
- Define DP state
- DP expression
- Base case
- Where is the answer?
- Table size
- Time complexity and space complexity
- Space optimization.
There are two ways to implement Dynamic programming:
1.Tabulation
2.Memoization
Tabulation
Tabulation is a way in which the results of the subproblems are computed first and then use it. It is a top down approach. It is generally implemented using iteration.
Memoization
Memoization is a way to call for the computation of subproblem result when we want to use it in bigger one. It is a bottom up approach. It is generally implement using recursion.
Space optimization
Space optimization is a way of decreasing the space used in DP. You need decrease the size of table. In order to do that you need to identify how many DP states are required to solve any problem. Here DP state is any state of subproblem. For example dp[i]= ith fibonacci number, this is a DP state.
Note: You cannot optimize your space in memozation. But You can use space optimization in tabulation method.
Practice problems for DP
