Dynamic Programming and Differential Equation

I’ve been reviewing algorithms lately. I feel like I’ve gone through Introduction to Algorithms pretty thoroughly — not at the level of classmates who started competitive programming in middle school, but enough to have a solid overall picture. Next time I might look into Combinatorial Optimization if I get the chance. (This reminds me that back in 7th grade I actually attended an informatics competition interest class at school — we were learning Pascal back then, which I’ve completely forgotten by now.)

On a side note, the cover features TWICE’s Nayeon. She’ll be coming to Seattle, where I live, for a concert in January next year. I’m still debating whether to buy tickets — feel free to message me if you’re interested.

Dynamic Programming

Starting with a small problem as an introduction: (The following DP overview is generated by ChatGPT — feel free to skip if you already have a solid foundation.)

Rod Cutting Problem

The rod cutting problem is a classic introductory example of dynamic programming:

Given a rod of length n and a price array p[i] (representing the price of a rod of length i), find the cutting scheme that maximizes revenue.

I. Brute Force

The most naive approach:

For each length n, try making the first cut at every possible position i = 1 ~ n:

Revenue = p[i] + CUT-ROD(n - i)

This enumerates all possible cutting combinations, essentially traversing the entire recursion tree.

CUT-ROD(p, n)
if n == 0
    return 0
q = -∞
for i = 1 to n
    q = max(q, p[i] + CUT-ROD(p, n - i))
return q

Time Complexity:

\[T(n) = 1 + \sum_{j=0}^{n-1} T(j)\]

Whether derived directly or by mathematical induction, the time complexity is $O(2^n)$.

II. Top-Down (Memoized Recursion)

Core idea: Avoid redundant computation by caching results in array r[].

When MEMOIZED-CUT-ROD-AUX(p, n, r) is called:

If r[n] already has a value, return it directly.
Otherwise, compute recursively and store the result.

Example: Calling MEMOIZED-CUT-ROD-AUX(*, 10, *) triggers:

10 → 9 → 8 → … → 1 → 0

Each length is computed only once on the first call; subsequent calls read directly from the table.

MEMOIZED-CUT-ROD(p, n)
let r[0..n] be a new array
for i = 0 to n
    r[i] = -∞
return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)
if r[n] ≥ 0
    return r[n]
if n == 0
    q = 0
else q = -∞
for i = 1 to n
    q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
r[n] = q
return q

Complexity: n+1 subproblems, each with an inner loop of 1..n → $O(n^2)$.

III. Bottom-Up Dynamic Programming

More straightforward: start from the smallest subproblems and fill the entire DP table.

Let r[j] = maximum revenue for a rod of length j.

BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        q = max(q, p[i] + r[j - i])
    r[j] = q
return r[n]

Complexity: Outer loop $n$, inner loop $n$ → $O(n^2)$.

IV. Extension: Recovering the Actual Cutting Plan

The above DP only records the maximum revenue. To know where each cut was made, we need to record the decision path by maintaining an additional array:

r[j]: optimal revenue
s[j]: the length of the first cut when the rod has length j

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] and s[1..n] be new arrays
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        if q < p[i] + r[j - i]
            q = p[i] + r[j - i]
            s[j] = i
    r[j] = q
return r and s

(End of AI-generated section)

In summary: top-down starts from n and works back toward the base case — like cooking a meal only when you’re hungry. Bottom-up starts from length 1 and progressively extends, with an outer pointer j: 1→n and an inner pointer i searching for the optimum at each length. The extended version simply records the cut positions.

Differential Equations

Consider a dynamical system with a physical background (any high schooler who understands Newton’s Second Law can follow this). Boundary conditions are essential — they constrain the solutions of the equation itself. This becomes even more significant in the context of eigenvalues (or spectra) of PDEs, and in the discrete setting they are key to determining the behavior of numerical matrices. I haven’t studied functional analysis deeply, but intuitively different boundary conditions seem to correspond to different differential operators. But I’m getting sidetracked.

In one sentence: the strength of differential equations is their intuitiveness.

So — can we write DP in an equally intuitive form? Yes, we can.

Here p is a known vector (in the rod cutting problem, it’s the value of each rod segment), and the Bellman equation is derived from the problem description as an optimality equation whose structure varies by problem. From this perspective, dynamic programming is simply numerical iteration from an initial value — completely analogous to solving a differential equation.

The DP Recipe (A Four-Step Framework)

Through solving LeetCode problems, I’ve gradually developed a sense that DP follows this pattern:

Input validation: Check whether inputs are reasonable and handle edge cases.
Initialize the DP table: If optimizing over two indices simultaneously, use a matrix. For example, LeetCode 72 and 174 both require tracking optimal values over both rows and columns, so matrix storage is used.
Set initial values: Just like differential equations, DP iteration needs initial values. For a vector, these are at position 0 or 1; for a matrix, these are the boundary rows/columns (top-left or bottom-right, depending on whether you propagate forward or backward). Some problems initialize along the diagonal and propagate to one side — such as the matrix chain multiplication problem, where by the associative law of multiplication you first compute matrices of shape i×k and k×j, minimizing intermediate dimensions.
Bellman equation structure: Write the optimality iteration based on the problem. There’s no shortcut here — working through small examples by hand is the best way to identify patterns. My personal approach to math: compute small cases, conjecture the general rule, then verify. From a numerical perspective, this is about how dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] influence dp[i][j]. (For forward propagation, the indices shift from -1 to +1 — symmetric with backward propagation.)

A Four-Step Quartet.

Summary

DP may look difficult and abstract at first, but viewed as a numerical dynamical system, it’s actually quite intuitive. Differential equations are a great analogy. If the continuous nature of differential equations feels too abstract, you can discretize them — I’ve verified personally that forward Euler discretization of a simple ODE numerically approximates the continuous solution quite well.

Dynamic Programming

Rod Cutting Problem

Differential Equations

The DP Recipe (A Four-Step Framework)

Summary

Enjoy Reading This Article?