Dynamic
Programming (DP) is an algorithmic technique for solving an
optimization problem by breaking it down into simpler sub-problems and
utilizing the fact that the optimal solution to the overall problem
depends upon the optimal solution to its sub-problems.
1. Overlapping Sub-problems
Sub-problems are smaller versions of the original problem. Any problem has overlapping sub-problems if finding its solution involves solving the same sub-problem multiple times.
2. Optimal Substructure Property
Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its sub-problems.