- Overlapping sub-problems – Solution of the sub-problems are re-used again and again while solving the main problem. Classic example, the factorial problem
F(n) = F(n-1) + F(n-2) while F(0) = 0 and F(1) = 1. It re-uses the solution of sub-problems again and again. - Optimal sub-structure – Optimal solution of a sub-problem leads to optimal solution to the main problem. Example, shortest path in a graph satisfies opitimal sub=structure property while the longest path finding doesn’t.
Dynamic problems can be solved using top-down approach or bottom-up approach.
- Top-down approach (Memoization) – Problem is split top down and solved using recursion. Results of individual steps are stored in a look-up array and re-used.
- Bottom-up approach (Tabulation) – Individual sub-problems are solved first leading to the solution of the problem in the end.
Dynamic programming generally deals with opitmization problems. Look for qualifying words such as least, minimum, maximum to spot the dynamic programming problems.
Vs Divide and Conquer
Divide and conquer deals with non-overlapping sub-problems while the dynammic programming deals with overlapping sub-problems.
Vs Greedy approach
Greedy finds locally optimal solution at every step making choices. Dynamic programming finds the solutions of sub-problems first and then make a choice to get the optimal solution.