CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

Solving Algorithmic Problems

There are two broad strategies. The first is to reduce the problem to something already
known: a data structure (array, linked list, dynamic array, sorted array, direct-access array,
hash table, avl tree, binary heap), a sorting algorithm (insertion-sort, selection-sort,
merge-sort, counting-sort, radix-sort, avl-sort, heap-sort), or a graph algorithm
(breadth-first-search, topological-sorting, dijkstra, bellman–ford). The second is
to design a recursive algorithm from scratch.
In a recursive algorithm the programme is constant in size while the input varies, and
correctness is argued by induction. It is useful to model the recursive calls as a graph in which
each subproblem is a vertex, with a directed edge from 𝐴 to 𝐵 whenever solving 𝐵 requires
the solution to 𝐴. For the recursion to terminate, this dependency graph must be acyclic. Its
shape often hints at the paradigm: a star suggests brute force, a chain suggests decrease-and-
conquer, a tree suggests divide-and-conquer, a dag suggests dynamic programming, and a
subgraph suggests a greedy or incremental approach.
In practice, the hard part is usually expressing the recurrence cleanly. A dependable checklist
is:

Subproblem definition Define a family of subproblems 𝑥 ∈ 𝑋 , describing each one in words

in terms of its parameters. Subproblems are typically subsets of the input (prefixes,
suffixes, or contiguous substrings of a sequence), though sometimes extra subproblems
are needed to track partial state through auxiliary variables.

Relation Express each subproblem’s solution recursively in terms of smaller subproblems:

𝑥 (𝑖) = 𝑓 (𝑥 ( 𝑗), . . . ) for one or more 𝑗 < 𝑖.

Topological order Argue that the relation is acyclic, so the subproblems form a dag.

Base cases State solutions for all reachable independent subproblems: those where the
relation breaks down.

Original problem Show how to compute the solution to the original problem from one
or more subproblem solutions. If needed, use parent pointers to recover the actual
solution rather than just the objective function value.

Time analysis The total time is 𝑥 ∈𝑋 work(𝑥), or |𝑋 | · 𝑂 (𝑊 ) when every subproblem

Í
takes at most 𝑂 (𝑊 ) nonrecursive work. Here work(𝑥) counts only the nonrecursive
work in the relation; each recursive call is treated as 𝑂 (1).

merge-sort in a Recursive Framework

merge-sort on an array 𝐴 of 𝑛 elements can be written as a clean recursive specification:

Subproblems Let 𝑆 (𝑖, 𝑗) denote the sorted array built from elements in 𝐴[𝑖 : 𝑗], for 0 ≤ 𝑖 ≤
𝑗 ≤ 𝑛.

MARCH 1, 2026 PAGE 1 OF 7

CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

 
Recurrence Compute 𝑆 (𝑖, 𝑗) by splitting at 𝑚 = 𝑖+𝑗 2 , then merging the two recursive
results:
𝑆 (𝑖, 𝑗) = merge(𝑆 (𝑖, 𝑚), 𝑆 (𝑚, 𝑗)).

Topological order Evaluate subproblems in increasing interval length 𝑗 − 𝑖.

Base cases When the interval contains one element, 𝑆 (𝑖, 𝑖 + 1) = [𝐴[𝑖]].

Original target The full problem is 𝑆 (0, 𝑛).

Running time The recurrence is 𝑇 (𝑛) = 2𝑇 𝑛
2 + 𝑂 (𝑛), so 𝑇 (𝑛) ∈ 𝑂 (𝑛 log 𝑛).

The resulting subproblem dag is a tree, which is exactly the divide-and-conquer pattern.

Fibonacci Numbers
Suppose we want to compute the 𝑛 th Fibonacci number 𝐹𝑛 .

Subproblems 𝐹 (𝑖) = the 𝑖 th Fibonacci number 𝐹𝑖 for 𝑖 ∈ {0, 1, . . . , 𝑛}.

Relation 𝐹 (𝑖) = 𝐹 (𝑖 − 1) + 𝐹 (𝑖 − 2) (definition of Fibonacci numbers).

Topological order Increasing 𝑖.

Base cases 𝐹 (0) = 0, 𝐹 (1) = 1.

Original problem 𝐹 (𝑛).

def fib(n):
if n < 2: return n # base case
return fib(n - 1) + fib(n - 2) # recurrence

Since the recurrence branches into two subproblems at every step, the recursive calls form
a binary tree. The
 running
 time satisfies 𝑇 (𝑛) = 𝑇 (𝑛 − 1) + 𝑇 (𝑛 − 2) + 𝑂 (1) > 2𝑇 (𝑛 − 2),
giving 𝑇 (𝑛) ∈ Ω 2 2 , which is exponential. The culprit is redundant work: subproblem
𝑛

𝐹 (𝑘) is recomputed 𝐹 (𝑛 − 𝑘) times. Can we avoid this waste?

Re-using Subproblem Solutions

Although the recursive calls form a tree, the subproblem dependencies form a dag: many
branches lead to the same subproblem. Instead of recomputing each one, we can re-use
earlier results in one of two ways:

MARCH 1, 2026 PAGE 2 OF 7

CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

Top down Record subproblem solutions in a memo and re-use them (recursion + memoisa-
tion).

Bottom up Solve subproblems in topological sort order, usually via loops.

For Fibonacci, the dag has 𝑛 + 1 vertices (subproblems) and fewer than 2𝑛 edges (dependen-
cies), so the total work drops to 𝑂 (𝑛) additions.

# recursive solution (top down)

def fib(n):
memo = {}
def F(i):
if i < 2: return i # base cases
if i not in memo: # check memo
memo[i] = F(i - 1) + F(i - 2) # relation
return memo[i]
return F(n) # original

# iterative solution (bottom up)

def fib(n):
F = {}
F[0], F[1] = 0, 1 # base cases
for i in range(2, n + 1): # topological order
F[i] = F[i - 1] + F[i - 2] # relation
return F[n] # original

 𝑛 
to Θ(𝑛) bits, which can far exceed the machine

There is a subtlety: Fibonacci numbers grow
word size 𝑤. Each
 addition
 then costs 𝑂 𝑤 rather than 𝑂 (1), bringing the total to 𝑇 (𝑛) ∈
 𝑛 
2
𝑂 𝑛 𝑤 = 𝑂 𝑛 + 𝑛𝑤 .

MARCH 1, 2026 PAGE 3 OF 7

CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

Dynamic Programming
The name “dynamic programming” was coined by Richard Bellman, who reportedly chose
it to sound impressive enough to secure government funding: “dynamic” for updating,
“programme” for a plan or schedule.
The idea rests on a simple observation. Whenever a recursive solution exists, the problem
decomposes into subproblems,1 and the recursive algorithm implies a graph of computation.
Dynamic programming applies when these subproblem dependencies overlap, meaning the
dependency graph is a dag with at least some vertices of in-degree greater than one. Two
equivalent perspectives capture the technique: “recurse but re-use” (top down: record and
look up subproblem solutions) and “careful brute force” (bottom up: solve each subproblem
in topological order). Dynamic programming is especially natural for counting and optimisation
problems, where the recurrences are almost trivially correct.

Bowling
We are given 𝑛 pins labelled 0, 1, . . . , 𝑛 − 1, where pin 𝑖 has value 𝑣𝑖 . A ball can hit either a
single pin 𝑖 (scoring 𝑣𝑖 points) or two adjacent pins 𝑖 and 𝑖 + 1 (scoring 𝑣𝑖 · 𝑣𝑖+1 points). Once
hit, a pin is removed. The goal is to throw zero or more balls to maximise the total score. As
an example, consider the pin values [−1, 1, 1, 1, 9, 9, 3, −3, −5, 2, 2].

Bowling Algorithms
We begin with a divide-and-conquer approach for comparison:

Subproblems 𝐵(𝑖, 𝑗) = maximum score starting with just pins 𝑖, 𝑖 + 1, . . . , 𝑗 − 1, for 0 ≤ 𝑖 ≤

𝑗 ≤ 𝑛.
 
Relation Let 𝑚 = 𝑖+𝑗2 . Either hit 𝑚 and 𝑚 + 1 together, or don’t:

𝐵(𝑖, 𝑗) = max{𝑣𝑚 · 𝑣𝑚+1 + 𝐵(𝑖, 𝑚) + 𝐵(𝑚 + 2, 𝑗), 𝐵(𝑖, 𝑚 + 1) + 𝐵(𝑚 + 1, 𝑗)}.

Topological order Increasing 𝑗 − 𝑖.

Base cases 𝐵(𝑖, 𝑖) = 0, 𝐵(𝑖, 𝑖 + 1) = max{𝑣𝑖 , 0}.

Original problem 𝐵(0, 𝑛).

Time 𝑇 (𝑛) = 4𝑇 𝑛2 + 𝑂 (1), so 𝑇 (𝑛) ∈ 𝑂 (𝑛 2 ).

This algorithm is correct but quadratic, and it does not generalise well: allowing a larger ball
that hits three pins at once, for instance, would complicate the split considerably. A cleaner
approach uses suffix subproblems:
1This property is often called optimal substructure. It is a property of recursion, not just dynamic program-
ming.

MARCH 1, 2026 PAGE 4 OF 7

CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

Subproblems 𝐵(𝑖) = maximum score starting with just pins 𝑖, 𝑖 + 1, . . . , 𝑛 − 1, for 0 ≤ 𝑖 ≤ 𝑛.

Relation Locally brute-force what could happen with first pin (original pin 𝑖): skip pin, hit
one pin, hit two pins. Reduce to smaller suffix and recurse, either 𝐵(𝑖 + 1) or 𝐵(𝑖 + 2):

𝐵(𝑖) = max{𝐵(𝑖 + 1), 𝑣𝑖 + 𝐵(𝑖 + 1), 𝑣𝑖 · 𝑣𝑖+1 + 𝐵(𝑖 + 2)}.

Topological order Decreasing 𝑖 (for 𝑖 = 𝑛, 𝑛 − 1, . . . , 0).

Base cases 𝐵(𝑛) = 𝐵(𝑛 + 1) = 0.

Original problem 𝐵(0).

Time Θ(𝑛) subproblems · Θ(1) work in each, so total time 𝑇 (𝑛) ∈ Θ(𝑛) (assuming memoi-
sation).

This runs in linear time and generalises easily: changing the ball size merely adds more
branches to the relation. The subproblem dag is a chain with skip edges, so bowling reduces
to finding a maximum-weight path:

max{𝑣 0, 0} max{𝑣 1, 0} max{𝑣 2, 0}

𝐵0 𝐵1 𝐵2 𝐵3 ··· 𝐵𝑛

𝑣0 · 𝑣1 𝑣1 · 𝑣2 𝑣2 · 𝑣3

How to Relate Subproblem Solutions

The general approach to defining a relation is to find a question about the subproblem whose
answer, if known, would reduce it to one or more smaller subproblems. For bowling, that
question is “what happens with the first couple of pins?” We then locally brute-force
the question by trying every possible answer and keeping the best; in this case, taking the
maximum because the goal is to maximise. An equivalent perspective is to imagine correctly
guessing the answer, recursing on the reduced problem, and then checking all guesses to
return the best.
The key to efficiency is that the question should have a small (polynomial) number of possible
answers, so the brute-forcing step is cheap. Often, though not always, the nonrecursive work
in the relation equals the number of answers being tried.

MARCH 1, 2026 PAGE 5 OF 7

CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

Practice Problems
For each problem below, apply the full checklist: define the subproblems, state the relation,
argue a topological order, give the base cases, identify the original problem, and analyse the
running time.

1. A frog sits on stone 1 in a line of 𝑛 stones, where stone 𝑖 has height ℎ𝑖 . From stone 𝑖
the frog can jump to stone 𝑖 + 1 or stone 𝑖 + 2, paying |ℎ𝑖 − ℎ 𝑗 | energy for a jump to
stone 𝑗. Find the minimum total energy needed to reach stone 𝑛.

2. You are given 𝑛 integers 𝑎 0, 𝑎 1, . . . , 𝑎𝑛−1 . Select a subset of elements at non-adjacent

indices (no two chosen indices are consecutive) that maximises the sum of the selected
values.

3. An 𝑚 × 𝑛 grid has a non-negative integer value 𝑣𝑖,𝑗 at each cell. Starting at the top-left
cell (0, 0) and ending at the bottom-right cell (𝑚 − 1, 𝑛 − 1), you may move only right
or down at each step. Find a path that maximises the total value collected.

MARCH 1, 2026 PAGE 6 OF 7

CSE317 | DESIGN AND ANALYSIS OF ALGORITHMS TUTORIAL | DYNAMIC PROGRAMMING

References
Erik Demaine. “Dynamic Programming, Part 1: srtbot, Fib, dags, Bowling.” Lecture 15,
mit 6.006 Introduction to Algorithms, Spring 2020. [Link]

MARCH 1, 2026 PAGE 7 OF 7