It is one of the most commonly asked approach of problem solving during coding interview.
Dynamic Programming problems can be categorised into two types: Optimisation problems and Combinatorial problems.
- How to Identify if it is a DP problem or not : Build recursive solution and Identify the base cases. If smaller problems are called multiple times during recursion then the given problem can be solved by using dynamic programming.
- Decide if you want to implement it using Top down or bottom up approach : We recommend to compare the properties of both the approaches and undestand pros and cons of each. Usually most programmers prefer bottom up approach (Why? Think)
- Things to care during the bottom up approach : Size of the table, Table Initialisation, Iterative structure to fill the table and point in the table where your final solution get stored.
- Key ideas to learn : Understanding concepts, Doing practice and finding implementation patterns among problems