Common characterstics in dynamic programming

Dynamic Programming is an algorithm design technique for optimization problems: often minimizing or maximizing.

• Like divide and conquer, DP solves problems by combining solutions to subproblems.

• Unlike divide and conquer, subproblems are not independent.

Subproblems may share subsubproblems,
However, solution to one subproblem may not affect the solutions to other subproblems of the same problem. (More on this later.)

• DP reduces computation by:

Solving subproblems in a bottom-up fashion.
Storing solution to a subproblem the first time it is solved.
Looking up the solution when subproblem is encountered again.

• Key: determine structure of optimal solutions