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.