Dynamic

Programming
Part I
Dr. Hao Ma
Objectives
Dynamic Programming

Shortest paths in dags

Longest increasing subsequences

Edit Distance
 Define the subproblem
(state definition)
Dynamic
Establish the recurrence
Programm (state transition)
ing
Initialize and compute the
result
Step 1: Define the subproblem (state definition)

Identify a smaller version of the original problem that can help you build up
to the full solution.

Define what the state represents — often something like dp[i] or dp[i][j].

Clearly describe what dp[i] means in words (e.g., “the minimum cost to reach
step i” or “the number of ways to make sum i”).

Example: For the Fibonacci sequence, define dp[i] = the i-th Fibonacci
number.
Step 2: Establish the recurrence (state transition)

Find the relationship between the current state and previous states.

Write the recurrence relation that expresses dp[i] in terms of smaller

subproblems.

Think about choices or decisions that lead to the optimal (or total) result.

Example: dp[i] = dp[i-1] + dp[i-2]

Step 3: Initialize and compute the result

Set up the base cases that stop the recursion (e.g., dp[0], dp[1]).

Choose whether to use top-down (memoization) or bottom-up (tabulation)

computation.

Compute the final answer (often dp[n] or dp[n-1][m-1]).

Example: dp[0] = 0, dp[1] = 1, then fill up the table from i = 2 to n.

 Bottom-up DP
Dynamic recursion + memoization

Programm
ing Top-down DP
iteration + tabulation
 Algorithms to find Fn
Exponential algorithm (naïve recursion)

This is basically the definition of Fibonacci number. The

running time grows as fast as the Fibonacci numbers.
 Algorithms to find Fn
Polynomial algorithm (tabulation, bottom-up DP)

The required number of

basic computer steps used
by fib2 is linear in n.
 • You identify the order in which subproblems
must be solved.
• You iteratively fill out a table (often an array)
from the base cases up to the target.
Bottom-up • This avoids recursion and is often more
Dynamic memory- and time-efficient.
Programming • Example: Fibonacci (Bottom-Up)
(Tabulation)
 Algorithms to find Fn
Polynomial algorithm (Memoization, top-down DP)

The required number of

basic computer steps used
by fib3 is linear in n.
 • You write a recursive solution that directly expresses
the problem as smaller subproblems.
• You use a cache (memo) to store results of
subproblems so that each one is solved only once.
• The recursion “unfolds” from the big problem to
Top-Down smaller ones, then combines the answers as it
returns.
Dynamic • Example: Fibonacci (Top-Down)
Programming
(Memoization)
Dynamic Programming vs Divide and Conquer

• Breaks a problem into independent

Divide subproblems.
• Each subproblem is solved separately, and

and their results are combined.

• There’s no overlap — subproblems don’t reuse
results.
Conquer • Examples: Merge Sort, Quick Sort, Binary
Search.
Dynamic Programming vs Divide and Conquer

• Breaks a problem into overlapping subproblems.

Dynamic • Subproblems depend on each other’s results, so
we store and reuse them.
Program • Avoids recomputation by using memoization
(top-down) or tabulation (bottom-up).
ming • Examples: Fibonacci numbers, Knapsack
problem, Shortest paths
 Dynamic Programming:

Divide → Solve overlapping parts →

Reuse results
In Short
Divide and Conquer:

Divide → Solve independently →

Combine
 Shortest paths in Directed Acyclic Graph
(DAG)
Review: a DAG is a directed graph with no directed cycles. The nodes of a DAG can be linearized;
that is, they can be arranged on a line so that all edges go from left to right
• The only ways to reach D are through its
predecessors, B or C.
• Define dist(x) as the distance from S to node x.
• To find the shortest path to D, we simply need to
compare these two possible routes:
• A similar relationship holds for every node.
• Compute distance values in the left-to-right order of the linearized DAG.
• By the time we reach a node v, all necessary information to compute dist(v) is
already available.
• This ensures that each node’s distance can be calculated efficiently without
revisiting previous nodes.
Summary
• The algorithm is a bottom-up DP.
• The algorithm solves a collection of subproblems.
• Start with the smallest subproblem, dist(s) = 0, which is known
immediately.
• Progressively solve larger subproblems — distances to vertices
further along in the linearization.
• A subproblem is considered large if it depends on solving many
other subproblems first.
• This approach ensures efficient computation by building on
previously solved subproblems.
Related • 64. Minimum Path Sum
• [Link]
Leetcode -path-sum/description/
Problems
Longest Increasing Subsequence (LIS)
• Given an array of numbers, find the length of the longest strictly
increasing subsequence.
• Example:
Input: [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: One LIS is [2, 3, 7, 101].
• Notes:
• A subsequence does not need to be contiguous.
The DAG of increasing subsequences
Dynamic Programming approach
• The DP philosophy here: To solve a complex problem, we break it
into a set of subproblems. These subproblems are organized in a
specific order, and we define a relationship showing how the
solution to each subproblem can be constructed from the
solutions to smaller, previously solved subproblems.

• Step 1: Define the subproblem (state):

Let dp[i] = length of the LIS ending at index i.

Dynamic Programming Approach
• Step 2: Recurrence relation (transition):
dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]
• If no such j exists, dp[i] = 1.
• This means: the LIS ending at i can extend any previous LIS that ends
with a smaller number.

• Step 3: Initialization:
dp[i] = 1 for all i (every element alone is a subsequence of length 1).

• Step 4: Compute the result:

LIS length = max(dp[0], dp[1], ..., dp[n-1]).
Related • 300. Longest Increasing Subsequence
• [Link]
Leetcode increasing-subsequence
Problems
 • What’s the time complexity of Dynamic Programming for
LIS?

• Idea of the Binary Search Approach

• Instead of keeping all possible increasing subsequences,
Another we maintain an array sub such that:
• sub[i] = the smallest possible tail of an increasing
approach: subsequence of length i+1.
• This array is not the actual subsequence, but its
Binary- length is the length of LIS.

search • We process each number in nums and decide where it fits

in sub using binary search:
• If the number is larger than all elements in sub,
append it.
• Otherwise, replace the first element in sub that is ≥
the number (found via binary search).
 nums = [10, 5, 8, 3, 9]

• Step by step:

Another • 10 → sub = [10]

approach: • 5 → sub = [5] (replace 10)

Binary-
search • 8 → sub = [5, 8] (append 8)

• 3 → sub = [3, 8] (replace 5 with 3)

• 9 → sub = [3, 8, 9] (append 9)

 If the question asks for the actual longest
increasing sequence instead of just its
length:
Extension • How can we modify the DP approach to return
the sequence?
• How can we modify the Binary Search
approach to return the sequence?
 • Edit distance (also called Levenshtein distance)
is a way to measure how different two strings are.

• It’s defined as the minimum number of operations

needed to transform one string into another.

• The Allowed Operations:

Edit • Insertion – insert a character.
distance Example: transforming "cat" → "cart": insert "r" →
"cart".

• Deletion – delete a character.

Example: "cart" → "cat": delete "r".

• Substitution – replace a character with

another.
Example: "cat" → "bat": replace "c" with "b".
Example
• Compute edit distance between "kitten" and "sitting":
• Operations:
• "kitten" → "sitten" (substitute 'k' → 's')
• "sitten" → "sittin" (substitute 'e' → 'i')
• "sittin" → "sitting" (insert 'g')
• Edit distance = 3
Example
• Compute edit distance between ”SNOWY" and ”SUNNY":
 • What are the subproblems?
• The subproblem is the edit distance
between some prefix of the first string, and
some prefix of the second string
A dynamic
• We define E[i,j] as the edit distance
programmin between the first i characters of string x
g solution and the first j characters of string y.

• How to express E[i, j] in terms of smaller

subproblems?
The rightmost column can only be

It’s not difficult to get:

Bottom-up DP (tabulation)
 • 62. Unique Paths
• [Link]
paths/description/

Related
• 63. Unique Paths II
Leetcode • [Link]
Problems paths-ii

• 120. Triangle
• [Link]
Dynamic
Programming
Part II
Dr. Hao Ma
Objectives

Knapsack Problem

Chain matrix multiplication

Independent sets in trees

Knapsack Problem: The Burglar’s Dilemma
Scenario

• A burglar finds more loot than expected

• His bag can carry up to W pounds
• There are n items, each with:
• Weight: w₁, w₂, …, wₙ .
• Value: v₁, v₂, …, vₙ
• Assume all wi and W are integers

Goal

• Choose the most valuable set of items without

exceeding the weight limit.
Variant 1: Knapsack with repetition
i.e.: there are unlimited quantities of each item available
Subproblem:
K(w) = maximum value achievable with a knapsack of capacity w

Transition:

Algorithm:
 • Each capacity 0, 1, . . . , W is a node.

Graph • For each item i and capacity w ≥ wi:

Interpretation • Edge :(w − wi) → w with weight vi

• No cycles ⇒ Directed Acyclic Graph.

Graph Interpretation: example

• Capacity W=6
• Items:
• Item 1: w1=2,v1=3
• Item 2: w2=3,v2=4
• DAG nodes: 0,1,…,6
• Edges correspond to “adding an
item”:
• 0→2 (+3), 2→4 (+3), etc.
• 0→3 (+4), 3→6 (+4), etc.
 • 322. Coin Change
• [Link]
change
Related
Leetcode • 518. Coin Change II
• [Link]
Problems change-ii
(unbounded
Knapsack) • 279. Perfect Squares
• [Link]
squares
Variant 2: Knapsack without repetition
Subproblem:
K(w, j) = maximum value achievable with a knapsack of capacity w and items 1,…,j

Transition:
• The first case is when item j is needed to achieve the optimal value
• The second case is when item j is not needed

Algorithm:
 • 416. Partition Equal Subset Sum
Related • [Link]
Leetcode equal-subset-sum
Problems
(0/1 • 496. Target Sum
• [Link]
Knapsack) sum
 • Goal: Determine the most efficient way to
multiply a sequence of matrices.
• Multiplying matrices is associative, but the
Matrix Chain order of multiplication affects the cost.
Multiplication • Each multiplication of two matrices of sizes
p×q and q×r costs pqr scalar multiplications.
Problem
• Example:
cost of (AB)C ≠ cost of A(BC)
• Same result, different computation cost
Matrix Chain • Number of possible parenthesizations grows
exponentially with the number of matrices.
Multiplication
Problem • Challenge: Find the parenthesization that
minimizes the total cost.
Matrix Chain Multiplication Problem

• The parenthesization of matrices can be

represented as a binary tree.
• Leaves of the tree → individual matrices.
• Root → final product of the
multiplication.
• Interior nodes → intermediate products.
For a tree to be optimal, • Different multiplication orders
its subtrees must also be optimal correspond to different full binary trees
with n leaves.
Matrix Chain Multiplication
Subproblem:

Transition:
Matrix Chain Multiplication
 • The subproblems constitute a two-
dimensional table
Matrix Chain • Each of whose entries takes O(n) time to
Multiplication compute.
• The overall running time is thus O(n^3).
Independent sets in trees

• Independent set: A set of vertices

in a graph such that no two vertices
in the set are adjacent.

• Example: In a tree (which is an

acyclic connected graph), any set of
non-adjacent nodes forms an
independent set.
Size of Largest Independent sets in
a tree ?
Subproblem:
I(u) = size of largest independent set of subtree hanging from u

Transition:
Suppose we already know I(w) for all descendants w of u,
meaning all its children, grandchildren, great-grandchildren,
and so on.
Size of Largest Independent
sets in a tree ?

• Two cases:
o either u is in this independent set,
or it isn't.

u included u not included