Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

1. Overlapping Subproblems #

Subproblems are smaller versions of the original problem. Any problem has overlapping sub-problems if finding its solution involves solving the same subproblem 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 subproblems.