Data Structure & Algorithm Takeaway: Dynamic Programming

TipWhat is dynamic programming?

Dynamic programming is an algorithm design paradigm for solving complex problems by breaking them down into simpler subproblems.

TipHow does dynamic programming work?

Suppose a algorithmic problem has a solution $S(n)$ with the parameter $n$. In some cases, the solution can be constructed efficiently from solutions like $S(n-1)$ to smaller subproblems with parameters less than $n$. This efficient relation between solutions between different parameters is called the transition function. The smaller subproblems can be further broken down into even smaller subproblems, and so on, until we reach the base case like $n=0$.

This is a recursive structure, however, we don’t do recursion directly but in the dynamic programming way. Once the problem can be easily broken down into smaller subproblems, the way that dynamic programming solves the problem is to start from the base case (like $S(0)$), first solve the smaller subproblems (like $S(1)$, $S(2)$, …), and then combine their solutions to get the solution of the original problem ($S(n)$) using the transition function.

TipWhat is the difference between dynamic programming and divide-and-conquer?

Problems with the above two properties can also be solved using both dynamic programming and divide-and-conquer. However, the key difference between dynamic programming and divide-and-conquer is that dynamic programming is used when the subproblems overlap, meaning that the same subproblems are solved multiple times. In contrast, divide-and-conquer is used when the subproblems are independent, meaning that each subproblem is solved only once.

TipWhy don’t we use recursion directly to solve the problem?

Because the subproblems overlap, using recursion directly to solve the problem would result in a lot of redundant calculations, leading to an exponential time complexity. Dynamic programming avoids this by storing the solutions to the subproblems in a table (usually an array or a matrix) and reusing them when needed, resulting in a polynomial time complexity.

TipPlease provide me a simple example of dynamic programming.

The Fibonacci sequence is a classic example of a problem that can be solved using dynamic programming. The transition function is explicitly defined in the problem. The Fibonacci sequence is defined as follows:

$$\begin{array}{rl}F(0)& =0\\ F(1)& =1\\ F(n)& =F(n-1)+F(n-2)\text{for }n\ge 2\end{array}$$

Let compute $F(5)$ as an example. We can break down the problem into smaller subproblems:

$$\begin{array}{rl}F(5)& =F(4)+F(3)\\ F(4)& =F(3)+F(2)\\ F(3)& =F(2)+F(1)\\ F(2)& =F(1)+F(0)\\ F(1)& =1\\ F(0)& =0\end{array}$$

The naive recursive approach to compute $F(n)$ would involve a lot of redundant calculations, leading to an exponential time complexity:

Fibonacci recursion tree

However, we can use dynamic programming to solve this problem efficiently by storing the results of the subproblems in an array and reusing them when needed. We can compute $F(2)$ and store the results so that we can compute $F(3)$ and don’t have to compute $F(2)$ all over again in the recursion tree.

Fibonacci dynamic programming transition relation.

TipIn which scenarios can we use dynamic programming?

If a problem has the following properties, we can use dynamic programming to solve it:

• The problem requires an answer that is a value, rather than a set of choices.
• The solution to the bigger problem can be constructed efficiently from solutions to smaller subproblems.
• The subproblems overlap, meaning that the same subproblems are solved multiple times.

TipWhat are the common forms of dynamic programmed variable?

Dynamic programmed variables can take various forms depending on the problem being solved.

• One DP variable:
  • The variable usually has a multi-step formula, where the step sizes are determined by some conditions in the problem. Example: Fibonacci sequence, knapsack problem.
• Two DP variable:
  • Two explicit separate things in the problem, which often corresponds to two DP variables.
  • Two DP variables for one thing in the problem. These two variables likely represent some dual concepts, like left / right, min / max, etc.
• Two-dimensional DP variable:
  • The problem involves a 2D thing, where the DP variable naturally becomes two-dimensional.
  • Intervals: The problem involves intervals or ranges, where the DP variable is defined on the start and end points of the intervals.
• Tree/Graph-like DP variable:
  • The problem involves a tree or graph structure, where the DP variable is defined on the nodes or edges of the tree/graph.

The dynamic programmed variable and its structure are usually not as simple as a one-dimensional array with one-step formula.

TipWhat are the common target things to solve using dynamic programming?

Optimal value (min / max / etc), ways to do something (number of ways, list of ways, etc), feasibility (whether something is possible or not), etc.

Some problems requires the argument that achieves the optimal value, which can be tracked using an auxiliary array during the DP process.