Dynamic programming is a design technique similar to divide and conquer, but with a big difference.
In Divide-and-Conquer algorithms a problem is partitioned into independent subproblems. The subproblems are solved recursively and then the results of the subproblems are combined to get the solution to the original problem.
Whereas, Dynamic Programming (DP) is used where the subproblems are dependent. A DP algorithm solves every subproblem just once, and the result of the subproblem is stored in a table, to avoid recomputation of the same subproblem in the future.
The word programming stands for tabular solution method, not for writing computer code.
DP is used to solve optimization (maximization and minimization) problems, where many possible solutions may exist.
Before discussing any specific problem, first, we need to understand some terminologies used in DP.
Optimal substructure
It is the optimal solutions of the subproblems which are used to find the optimal solution to a problem.
Overlapping subproblems
Subproblems need to be solved many times if the result is not memorized. These subproblems are known as overlapping subproblems, which are used many times to find the solution to the original problem.
Posts
No comments:
Post a Comment