> For the complete documentation index, see [llms.txt](https://cs-notes.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-notes.gitbook.io/algorithm-notes/outline/overview-6/overview.md).

# Overview

In the fields of computer science, economics, managerial sciences, mathematics and bioinformatics, [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) or dynamic optimization is similar to [divide-and-conquer](/algorithm-notes/outline/overview/overview.md) principle as to decompose a complex problem into smaller sub-problems.

## Fundamental Idea

In contrast to the paradigm of [DnC](/algorithm-notes/outline/overview/overview.md) 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](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) would store and reuse the solution when it was solved the first time (also known as [*memoization*](https://en.wikipedia.org/wiki/Memoization)), programming solutions all together.

The typical [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#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*](https://en.wikipedia.org/wiki/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*](https://en.wikipedia.org/wiki/Richard_E._Bellman).

## Comparing with [Greedy Algorithms](/algorithm-notes/outline/overview-7/overview.md)

It is often confusing to determine if the programming logic is built on [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) or [greedy algorithms](/algorithm-notes/outline/overview-7/overview.md). Both are adopted in favor of tackling *optimization problem*, and [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) seeks and combines the previous solutions for sub-problems to yield the final result while [greedy algorithms](/algorithm-notes/outline/overview-7/overview.md) chooses locally optimal solution in each run and not guarantee to have the optimal result.

For instance, in a [coin change problem](https://en.wikipedia.org/wiki/Change-making_problem) of finding a minimum number of coins with certain denominations added up to a specified amount, [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) is a killer solution than using [greedy algorithms](/algorithm-notes/outline/overview-7/overview.md) in that:

given a set of denominations: 1, 4, 5, 15, 20 and the specified amount 23; the [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) would yield an optimal solution of 15 + 4 + 4 while the [greedy algorithms](/algorithm-notes/outline/overview-7/overview.md) offers a non-optimal one 20 + 1 + 1 + 1.

wherein, [greedy algorithms](/algorithm-notes/outline/overview-7/overview.md) picks the largest one in the set of coins from the first run; [dynamic programming](/algorithm-notes/outline/overview-6/overview.md#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](/algorithm-notes/outline/overview-6/overview.md#dynamic-programming) type:

* [Fibonacci Numbers](/algorithm-notes/outline/overview-6/fibonacci-numbers.md) - a topic referring to [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number) that to find a ith such number.
* [Matrix-Chain Multiplication](https://github.com/aaronoah/algorithm-notes/tree/737083f3adcf6257062ab7dcb286a5fcf31232c6/docs/dynamic-programming/matrix-chain-multiplication.md) - solving the matrix dot multiplication in an most efficient way by least number of scalar multiplications in total.
* [LCS Problem](/algorithm-notes/outline/overview-6/lcs-problem.md) - a practical problem found in many scenarios such as DNA sequences detection.
* [Discrete Knapsack](https://github.com/aaronoah/algorithm-notes/tree/737083f3adcf6257062ab7dcb286a5fcf31232c6/docs/dynamic-programming/discrete-knapsack.md) - knapsack problem in a discrete version.