Introduction to Dynamic Programming
About me
My interests:
- Structural Bioinformatics
- Graph algorithms
- Representation learning
Some questions I ask:
- How can we efficiently search through graph databases?
- What kinds of patterns can we discover in datasets of graphs?
- Can we model biological systems using efficient data structures to learn about how they function?
Dynamic Programming (DP)
|
|
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
|
- Richard Bellman, 1950s, working at RAND institute.
- Picked the name "Dynamic Programming" to please his boss.
|
- Method for solving a large problem by breaking it down into smaller sub-problems.
Applications
- Bioinformatics: protein and RNA folding, sequence alignment
- Speech recognition: Viterbi's algorithm
- Time series modeling: Dynamic time warping
- Search: string matching
- Scheduling: weighted interval
- Music: Beat tracking
- Routing: shortest path problems
Objectives
After this lesson we should be able to:
Basic Intuition
First ingredient: Optimal Substructures
The optimal structure can be built by combining optimal solutions to smaller problems.
E.g. Fibonacci numbers
Recursive algorithm:
Second ingredient: Overlapping Substructures
The same subproblem's solution is used multiple times.
Call tree fib(6)
:
Recursive solution is .
Can we do better?

M-fib(n)
:
An example without overlapping subproblems.
Binary Search: Given a sorted array and a query element, find the index where the query occurs.
Call tree binary_search(A=[ 15, 22, 32, 36, 41, 63, 75], left=0, right=4, query=75)
:
Case study: Weighted Interval Scheduling
- Input: requests, labeled . Each request has a start time and an end time , and a weight .
- Output: a compatible subset of that maximizes .
is compatible iff all pairs of intervals in are non-overlapping.
- Uses: resource allocation for computer systems, optimizing course selection.
Example:
False start: greedy approach
- From "previous" lectures we know the greedy approach to the unweighted IS problem gives the optimal solution (i.e. pick item with earliest ending time)
Counterexample:
The weights force us to consider all possible subproblems (i.e. local choice is not enough).
A helper function
Let us sort all intervals by increasing finish time and let return the latest interval that is still compatible with .

First ingredient: Optimal Substructure?
-
Consider to be the optimal set of requests over all items .
-
Also consider the weight of the best solution up to as .
-
There are two cases for the last request, .:
Case 1
Case 2
Optimal Substructure
Let be the total weight of the optimal over intevals up to .
We can now write an expression for computing :
Ingredients
First algorithm
Now we can write down a recursive algorithm that gives us the maximum weight over .
compute_OPT(j)
:
Ingredient 2: Overlapping Substructures
Let's build the execution tree for our recursive algorithm on this example:

compute_OPT(6)
:
Runtime:
Ingredients
Memoization
- Key idea in DP: remember solutions to sub-problems you already computed.
New algo: M_compute_OPT(j)
Runtime:
Are we done?
- Recall is just a number, we want the set of intervals with the score … i.e. .
- Traceback is a key idea in DP. We reconstruct the solution backwards from the array using the recurrence.
- Obervation: We know that an interval belongs to if:
Now our DP execution has two steps:
- Fill
- Reconstruct solution from
Full Example

Fill and get :
Recap
- Dynamic Programming works well when we have a problem structure such that:
- Combining sub-problems solves the whole problem
- Sub-problems overlap
- We can often reduce runtime complexity from exponential to polynomial or linear.
- Steps to solving a problem with DP:
- Define subproblems:
- Write down the recurrence that relates subproblems.
- Recognize and solve the base cases.
- Implement a solving methodology. (e.g. memoization, tabulation is also an option)
General interest: RNA folding
- RNA molecules are essential to all living organisms.
- Knowing the sequence is easy but not so informative, knowing the structure is hard but tells us a lot about the molecule's function.

A Sketch of Nussinov's Algorithm
- First attempt at solving this problem
|
|
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
|
Ruth Nussinov, designed the first RNA folding algo in 1977. |
- In CS terms, an RNA is a string on a 4-letter alphabet.
- An RNA structure is a pair of indices over the string with certain constraints.

RNA folding rules
We use some fairly realistic constraints on admissible structures:
- Only
A-U
, U-A
and C-G
, G-U
form pairs
- Pairs shall not cross (nestedness).
- Start and end of a pair should be separated by at least spaces (remove steric clashes).
- The best structure is the one that forms the most pairs (stability). e.g each pair adds 1 to the score.
This lets us identify the problem structure needed for a DP solution:
Consider an optimal set of pairs between two indices , and the score of the olution . We have two cases for index :
Case 1. is not in :
Note we introduce a new variable 2 dimensional DP.
Case 2. is in :
Ingredients?
From this we can build our recurrence that fills the table up to .
Bonus Questions: What is the runtime for filling the table?
If you want an exercise sheet to learn how to implement this send me an email carlos@ozeki.io
.