Dynamic Programming and Optimal Substructure.

First step in dynamic algorithm design is defining optimal solution structure.

We'll say that problem shows optimal substructure, if it's optimal solution is optimal subsolutions function.

Common subproblem optimalization occurs when the same subproblem solution is used many times.

For example:

Let's compute: f(2) = (2*2) + (3*2) + (2*2).

We can lazily count (2*2) only once instead of twice.

We can find optimal substructure for this problem by constructing mathematical expression tree, where leaves are numbers and other nodes are mathematical operators.

Substructure would be structure of nodes in this tree, or order of computations.

Optimal solution for laziness (least number of computations) would be to count most common subproblems, (2*2) in this case, first.

in other examples, where 0 appears, laziness can be optimized even more, by 'cutting' subtrees that are multiplied by 0... and so on.

Source: [4].

See also: Dynamic Programming, How Stitie Machine can help to code Dynamically?.

No comments:

Post a Comment