Dynamic Programming

In the fields of computer science, economics, managerial sciences, mathematics and bioinformatics, dynamic programming or dynamic optimization is similar to divide-and-conquer principle as to decompose a complex problem into smaller sub-problems.

Fundamental Idea

In contrast to the paradigm of DnC that sub-problems are independent, dynamic programming is adopted to solve interleaved sub-problems wherein multiple sub-problems might have common smaller sub-problems. And for each repetitive sub-problem, dynamic programming would store and reuse the solution when it was solved the first time (also known as memoization), programming solutions all together.

The typical dynamic programming algorithm is developed in steps follow:

1. Characterize the optimal sub-structures along with possible moves. (think of it as finding a DAG for a solution path)

2. Define the recurrence relations of sub-problems.

3. Compute recursively or iteratively in a bottom-up fashion or top-down with memoization fashion.

4. Construct an overall optimal solution or combining solutions of sub-problems.

Noted that the word programming does not stand for computer programming but a tabulation method that was invented by R. Bellman.

Comparing with Greedy Algorithms

It is often confusing to determine if the programming logic is built on dynamic programming or greedy algorithms. Both are adopted in favor of tackling optimization problem, and dynamic programming seeks and combines the previous solutions for sub-problems to yield the final result while greedy algorithms chooses locally optimal solution in each run and not guarantee to have the optimal result.

For instance, in a coin change problem of finding a minimum number of coins with certain denominations added up to a specified amount, dynamic programming is a killer solution than using greedy algorithms in that:

given a set of denominations: 1, 4, 5, 15, 20 and the specified amount 23; the dynamic programming would yield an optimal solution of 15 + 4 + 4 while the greedy algorithms offers a non-optimal one 20 + 1 + 1 + 1.

wherein, greedy algorithms picks the largest one in the set of coins from the first run; dynamic programming takes into account the solutions to each small sub-problem that are related to each other during iterations.

Table of Contents

The following example questions can be categorized into dynamic programming type:

• Fibonacci Numbers - a topic referring to Fibonacci sequence that to find a ith such number.
• Matrix-Chain Multiplication - solving the matrix dot multiplication in an most efficient way by least number of scalar multiplications in total.
• LCS Problem - a practical problem found in many scenarios such as DNA sequences detection.
• Discrete Knapsack - knapsack problem in a discrete version.