Dynamic
Programming is an algorithmic model that solves a given complex problem by
breaking it down into a collection of simpler subproblems and stores the
results of subproblems to avoid computing the same results again.

A
problem has two below properties can be solved using Dynamic programming.

**1) Overlapping subproblems**

**2) Optimal substructure**

**1) Overlapping subproblems**

If
the problem can be broken down into subproblems which are reused several times
or a recursive algorithm for the problem solves the same subproblem over and
over rather than always generating new subproblems. Computed solutions to
subproblems are stored in a table so that these don’t have to recomputed.

So
Dynamic Programming is not useful when there are no common (overlapping)
subproblems because there is no point storing the solutions if they are not
needed again.

**2) Optimal substructure**

A
problem is said to have optimal substructure if an optimal solution of the
given problem can be obtained by using optimal solutions of its subproblems.
This property is used to determine the usefulness of dynamic programming and
greedy algorithms for a problem.

## No comments:

## Post a Comment