Dynamic Programming
"Programming" here is an old word for optimization (as in "linear programming") — nothing to do with writing code. The problem, straight from the lecture:
Given a grid of numbers, walk from the top to the bottom. At each step you may go straight down, down-left, or down-right. Add up the numbers you land on. Find the path with the smallest total.
Enumerating every path is hopeless — the number of paths grows exponentially with the grid height. Dynamic programming finds the best one in a single sweep by reusing the answers to overlapping subproblems. Below it all runs live in your browser.
begin
using PlutoUI, WasmMakie
endThe cost landscape
Here is our grid of costs, shown as an image — dark is cheap, bright is expensive. There's a low-cost "valley" winding down it. Drag tilt to bend the valley left or right, and size to change the grid. The cheapest top-to-bottom path is drawn in red, recomputed instantly each time you move a slider.
size n =
valley tilt =
begin
# ── WasmMakie helpers (flat, column-major; row 1 drawn at the TOP) ──────────
function rgb_figure(pix::Vector{NTuple{4,Float64}}, nr::Int, nc::Int; px::Int = 360)
fig = Figure(size = (px, max(40, round(Int, px * nr / nc))))
ax = Axis(fig[1, 1])
hidedecorations!(ax)
hidespines!(ax)
image!(ax, (0.0, Float64(nc)), (0.0, Float64(nr)), pix,
Int64(nc), Int64(nr); interpolate = false)
fig
end
function gray_figure(vals::Vector{Float64}, nr::Int, nc::Int; px::Int = 360)
pix = Vector{NTuple{4,Float64}}(undef, nr * nc)
for k in 1:(nr * nc)
v = vals[k]
pix[k] = (v, v, v, 1.0)
end
rgb_figure(pix, nr, nc; px = px)
end
end# Build an n×n cost grid (row-major, row 1 = top). A low-cost valley drifts across
# the grid as `tilt` changes, plus a little ripple texture. Everything is a function
# of the coordinates — no randomness (not wasm-friendly), fully reproducible.
function landscape(n::Int, tilt::Float64)
costs = Vector{Float64}(undef, n * n)
cc = (n + 1.0) / 2.0
for i in 1:n
for j in 1:n
vc = cc + tilt * (i - cc) # valley centre at row i
dd = abs(j - vc)
v = 0.30 + 0.45 * dd / n + 0.12 * (0.5 + 0.5 * sin(0.9 * i + 0.7 * j))
v < 0.05 && (v = 0.05)
v > 0.98 && (v = 0.98)
costs[(i - 1) * n + j] = v
end
end
return costs
end# Dynamic programming: dp[i,j] = cheapest total from cell (i,j) down to the bottom.
# Fill from the second-to-last row upward; each cell adds its own cost to the cheapest
# of the (up to) three cells below it. THIS is the reuse of overlapping subproblems.
function solve_dp(costs::Vector{Float64}, n::Int)
dp = copy(costs)
for i in (n - 1):-1:1
for j in 1:n
best = dp[i * n + j] # (i+1, j)
if j > 1 && dp[i * n + j - 1] < best
best = dp[i * n + j - 1]
end
if j < n && dp[i * n + j + 1] < best
best = dp[i * n + j + 1]
end
dp[(i - 1) * n + j] = costs[(i - 1) * n + j] + best
end
end
return dp
end# Walk the filled table from the cheapest top cell downward, always stepping to the
# cheapest of the three cells below. Returns the column visited at each row.
function trace_path(dp::Vector{Float64}, n::Int)
path = Vector{Int}(undef, n)
sj = 1
for j in 2:n
dp[j] < dp[sj] && (sj = j) # cheapest entry on the top row
end
path[1] = sj
for i in 1:(n - 1)
j = path[i]
nj = j
best = dp[i * n + j]
if j > 1 && dp[i * n + j - 1] < best
best = dp[i * n + j - 1]
nj = j - 1
end
if j < n && dp[i * n + j + 1] < best
nj = j + 1
end
path[i + 1] = nj
end
return path
endlet
costs = landscape(n, tilt)
dp = solve_dp(costs, n)
path = trace_path(dp, n)
# paint the landscape gray, then the optimal path red
pix = Vector{NTuple{4,Float64}}(undef, n * n)
for i in 1:n
for j in 1:n
v = costs[(i - 1) * n + j]
pix[j + (n - i) * n] = (v, v, v, 1.0)
end
end
for i in 1:n
j = path[i]
pix[j + (n - i) * n] = (0.95, 0.25, 0.20, 1.0)
end
rgb_figure(pix, n, n)
endThe trick: overlapping subproblems
The naive method re-walks the whole grid for every path. But notice: the cheapest way down from a cell only depends on the three cells below it. So if we already know the best total-to-the-bottom for every cell in row $i+1$, each cell in row $i$ is just
$$\text{dp}[i,j] = \text{cost}[i,j] + \min\big(\text{dp}[i{+}1,j{-}1],\ \text{dp}[i{+}1,j],\ \text{dp}[i{+}1,j{+}1]\big).$$
One sweep from the bottom up fills the whole table. Below is that cost-to-the-bottom table for the same grid — dark cells are cheap launch points. The optimal path simply follows the dark gradient down from the cheapest top cell.
let
costs = landscape(n, tilt)
dp = solve_dp(costs, n)
# normalise dp to 0..1 for display
lo = dp[1]
hi = dp[1]
for k in 2:(n * n)
dp[k] < lo && (lo = dp[k])
dp[k] > hi && (hi = dp[k])
end
span = hi - lo
span <= 0.0 && (span = 1.0)
disp = Vector{Float64}(undef, n * n)
for i in 1:n
for j in 1:n
disp[j + (n - i) * n] = (dp[(i - 1) * n + j] - lo) / span
end
end
gray_figure(disp, n, n)
endWhy it's a huge speed-up
Naive: enumerate every path → about $3^{n}$ of them for an $n$-row grid. At $n=40$ that's already more paths than there are atoms in your body.
Dynamic programming: fill an $n \times n$ table once → about $n^2$ work. At $n=40$, 1,600 little
minoperations. Done.
Same answer, exponentially less effort, because we remembered each subproblem instead of recomputing it. Next up: this exact idea carves seams out of images.