Dynamic Programming 1/n: What Is Dynamic Programming?

I’ve heard the term “dynamic programming” a hundred times but never really understood it— I don’t even know what it’s used for. However, its frequent appearance indicates it’s worth learning.

What Is Dynamic Programming?

Before learning dynamic programming, you need to clearly understand what it is. Many textbooks dive straight into content without explaining its core idea.

Dynamic Programming (DP for short) is a programming paradigm, not a specific algorithm. It breaks down a large problem into smaller subproblems through recursion—mathematically speaking, it can be expressed as a polynomial. This allows solving problems of different scales with minimal changes to the code (a key advantage of recursion).

A quick note: Divide and Conquer (D&C for short) also splits large problems into smaller ones, but D&C uses direct splitting, while dynamic programming uses recursive splitting—it’s important to distinguish between the two. Here are two examples to illustrate:

Note: Dynamic programming is not recursion itself; it merely leverages recursion. Divide and Conquer can also use recursion (e.g., quicksort).

When adding two arrays, you can split the task into n pairs and compute them together. For example, calculate a[1]+b[1] and a[10]+b[10] in the first iteration, a[2]+b[2] and a[11]+b[11] in the second, and so on until all ten elements are processed. This splitting can be sequential or random, but the split parts have no correlation—for instance, a[1] has no dependency on a[2].

In dynamic programming, however, each split (or most splits) has correlations or dependencies. A classic introductory example is the Fibonacci sequence. Except for the first two elements, every element in the Fibonacci sequence is the sum of the two preceding ones. Its mathematical expression is:

This is also known as the Bellman equation. They are the same concept, but “dynamic programming” is commonly used in algorithms, while “Bellman equation” is used in optimization.

We can derive the nth Fibonacci number through iteration:

From this, you can see why concepts like topological sort and critical path are related to dynamic programming—their splits involve inherent correlations. By leveraging these correlations (or constraints), we can find an optimal solution. Thus, dynamic programming is typically used to solve optimization problems. If you browse DP-related questions on LeetCode, you’ll notice many include keywords like “shortest,” “fastest,” or “most efficient.”

How to Implement Dynamic Programming?

Designing a dynamic programming algorithm generally involves six steps:

• Subproblem Definition: Determine what the subproblems are. For the Fibonacci sequence, the subproblem is $fib(n) = fib_n$.
• Relate Subproblem Solutions to Recursive Structures: For example, calculating a Fibonacci number can be done by recursively calling the fib() function (or using a for loop, which is faster).
• Use Topological Sort to Ensure Acyclic Subproblems: This sounds abstract, but think of recursive subproblems (or function calls) as a graph—topological sorting ensures a path without cycles. The initial subproblem with an in-degree of 0 is the first call. A cyclic graph would cause an infinite loop, indicating a flawed algorithm. (I once read in a senior engineer’s memoir that a student accidentally crashed a school’s mainframe by writing a cyclic Fibonacci algorithm when first learning programming.)
  

  You can also use other algorithms to check for cycles.

• Relationship Between Base Cases: This is a prerequisite for steps 1 and 2—understanding this relationship allows defining subproblems and recursive structures. For example, each Fibonacci number (after the first two) is the sum of the previous two.
• Solve the Original Problem Using Subproblem Solutions: Combine subproblem results to address the initial large problem.
• Runtime Analysis: The time complexity of the Fibonacci sequence algorithm is exponential.

However, these steps can be simplified to four:

• Relationship between base cases.
• Subproblem definition.
• Relate subproblem solutions to recursive structures.
• Use topological sort to ensure acyclic subproblems.

A Deep Dive into Runtime

The analyzed runtime of an algorithm is not directly tied to its actual execution time—this is emphasized in almost every first algorithm class. Thus, you may need to adjust the recursive structure in practice. For example, the Fibonacci sequence:

Using recursive function calls (the code below matches our subproblem formula), calculating the 45th term takes approximately 5.58 seconds:

int fib(int n) {
    if(n == 0) return 0;
    return (n > 2) ? fib(n-1) + fib(n-2) : 1;
}

But using a for loop yields a massive speedup—up to 6–7 orders of magnitude faster:

long int fib(int n) {
    long int pre_pre = 0, pre = 1, cur = 0;
    if(n == 0) return 0;
    if(n == 1) return 1;
    for(int i = 1; i < n; i++) {
        cur = pre + pre_pre;
        pre_pre = pre;
        pre = cur;
    }
    return cur;
}

Two reasons explain this difference:

1. System Overhead: Recursive function calls require allocating new function stacks, handling inputs/outputs, and managing returns—all of which add significant overhead. A for loop, by contrast, is just a sequence of addition operations, making it much faster.
2. Redundant Calculations: Calculating fib(n) and fib(n-1) both require computing fib(n-2)—leading to substantial redundant work. A for loop avoids this by computing values incrementally. This optimization is called memoization, so dynamic programming is sometimes described as $DP = SRTBOT + memoization$.

SRTBOT stands for “recursive algorithms design paradigm.”

Thus, the choice of implementation depends on the specific scenario.

The next article will focus on practical problems. We’ll practice dynamic programming through two classic examples: Dynamic Programming 2/n: Practicing DP with Concrete Problems (Climbing Stairs, House Robber).

I hope these will help someone in need~