Richard Ernest Bellman, an American mathematician, introduced the concept of Dynamic Programming (DP) in the 1950s, to solve complex problems by breaking them into smaller, manageable subproblems.

Dynamic programming is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.

Here programming is not a computer program. It is a process of obtaining the plan to get the optimal solution.

characteristics of Dynamic Programming

A problem is generally suitable for Dynamic Programming when it has two important characteristics:

1. Optimal substructure: A specified problem has the optimal substructure property if its optimal solution can be derived from the optimal solutions of its subproblems.
2. Overlapping subproblems: The problem in question should be able to be broken down into a cascade of reusable subproblems, or a recursive algorithm can repeatedly solve subproblems without generating new ones.

Features of dynamic programming

1. Principle of optimality: For any optimal sequence of decisions, whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequence with regard to the state resulting from the first decision.
2. The total number of decision sequences is exponential in the number of decisions, so dynamic programming algorithms often have a polynomial complexity. If there are d choices for each of the n decisions to be made, then there are $d^n$ possible decision sequences.
3. Optimal solutions to subproblems are retained to avoid recomputing their values. Values are stored in tables.

What is principal of optimality?

Principle of optimality: Suppose that in solving a problem, we have to make a sequence of decisions D1, D2, …, Dn. If this sequence is optimal, then the last k decisions, 1 < k < n must be optimal.

e.g. the shortest path problem If i, i₁, i₂, …, j is a shortest path from i to j, then i₁, i₂, …, j must be a shortest path from i1_{to j.}

If a problem does not possess these properties, dynamic programming cannot be applied to the problem.

Two main approaches to Dynamic Programming

Memoization (Top-Down)

Uses recursion.

Stores calculated results.

Reuses stored results when needed.

Tabulation (Bottom-Up)

Uses iteration.

Solves smaller subproblems first.

Stores results in a table.

Applications of dynamic programming

1. Optimal binary search tree
2. 0/1 knapsack problem
3. All pairs shortest path problem
4. Traveling salesperson problem
5. Reliability design