Dynamic Programming
Dynamic Programming
▪ A technique to solve complex problems by breaking them into overlapping
subproblems and storing their solutions to avoid recomputation
▪ “Programming” refers to a tabular method, not to writing computer code
▪ It applies when the subproblems overlap—that is, when subproblems share
subsubproblems
▪ A dynamic-programming algorithm solves each subsubproblem just once and then
saves its answer in a table, avoiding the work of recomputing the answer every time it
solves each subsubproblem
▪ Typically applied to optimization problems
▪ Find all possible solutions for a given problem and select the best solution
▪ Adopts Memoization or Tabulation method
2
Dynamic Programming – Examples of Problems
▪ Fibonacci numbers
▪ Factorial
▪ 0/1 Knapsack
▪ Longest Common Subsequence (LCS)
▪ Matrix Chain Multiplication
▪ Shortest path (Bellman-Ford algorithm)
▪ Maximum subarray problem
3
Dynamic Programming – Not suitable
▪ Not suitable for
▪ Problems without overlapping subproblems
▪ Problems without optimal substructure (cannot build optimal solution from
subproblems)
4
Dynamic Programming
▪ Memoization (Top-Down):
▪ Solve recursively and store results in a table for reuse
▪ Solve from problem to subproblem
▪ Tabulation method (Bottom-Up):
▪ Solve smaller subproblems first and build up the solution iteratively
▪ Solve from subproblem to problem
5
Dynamic Programming
▪ Example: Fibonacci numbers
F(n)=F(n−1)+F(n−2), F(0)=0, F(1)=1
Memoization: Tabulation:
6
Dynamic Programming - Elements
▪ Optimal substructure: Constructing the optimal solution of the main problem from
optimal solutions of its subproblems
▪ Overlapping subproblems: Repetition of subproblems
▪ Reconstructing an optimal solution
▪ Memoization
7
Dynamic Programming – Steps
1. Characterize the structure of an optimal solution:
▪ Check whether the problem has optimal substructure
2. Recursively define the value of an optimal solution:
▪ Define the subproblems and Write a recurrence relation with base case
▪ The recurrence defines the solution in terms of smaller subproblem
3. Compute the value of an optimal solution, typically in a bottom-up fashion:
▪ Compute the solution and store it to avoid recomputation
4. Construct an optimal solution from computed information:
▪ Find actual solution by tracing the DP table
8
Longest Common Subsequence (LCS)
▪ Given two sequences X = (x1, x2, … xm) and Y = (y1, y2, … yn)
▪ Goal: Find a maximum length common subsequence of X and Y
▪ Longest common subsequence: the longest sequence of characters that appear left-
to-right (but not necessarily contiguously) in both strings.
▪ Biological applications: compare the DNA of two (or more) different organisms.
▪ A strand of DNA consists of a string of molecules called bases: adenine, cytosine,
guanine, and thymine {A, C, G, T}.
▪ DNA of one organism may be S1= ACCGGTCGAGTGCGCGGAAGCCGGCCGAA,
DNA of another organism may be S2= GTCGTTCGGAATGCCGTTGCTCTGTAAA.
▪ Determine how “similar” the two strands are, as some measure of how closely related
the two organisms are.
▪ The longest strand S3 is GTCGTCGGAAGCCGGCCGAA.
9
Longest Common Subsequence
▪ For example, consider:
X = (A, B, C, B, D, A, B)
Y = (B, D, C, A, B, A)
10
Longest Common Subsequence
▪ Step1: Optimal substructure: An LCS of two sequences contains LCSs of their
prefixes
▪ Case 1: An optimal solution to the full problem contains an optimal solution to a
smaller subproblem
▪ Case 2 and 3: The optimal solution comes from the best of smaller subproblems
11
Longest Common Subsequence
▪ Step2: Recursive Solution:
12
Longest Common Subsequence
▪ Step4: Constructing an LCS
13
Longest Common Subsequence
▪ Step3: Computing the length of an LCS
14
Longest Common Subsequence – Example
▪ X = {A, B, C, B, D, A, B}
▪ Y = {B, D, C, A, B, A}
15
Matrix Chain Multiplication
▪ Matrix-chain multiplication problem: Given a chain (A1, A2, …, An) of n matrices,
for i = 1, 2, …, n, matrix Ai has dimension pi-1×pi , fully parenthesize the product
A1A2...An in a way that minimizes the number of scalar multiplications
▪ Determine how to optimally parenthesize a matrix chain
▪ Goal: To determine an order for multiplying matrices that has the lowest cost
▪ Input: sequence of dimensions (p0, p1, …, pn)
▪ Not entail actually multiplying matrices
▪ Resultant matrix is identical, but difference in cost
▪ Brute force grows exponentially, DP reduces to O(n3)
16
Matrix Chain Multiplication
A1 (10 ×30), A2 (30 ×5), A3 (5 ×60)
17
Matrix Chain Multiplication
Number of possible paranthesizations:
18
Matrix Chain Multiplication - Applications
▪ Database Query Optimization: SQL queries involving multiple joins, the order of
joins affects performance; Choose least cost join order
▪ Compiler optimization: Loop optimization and expression tree evaluation
▪ Deep learning and neural networks: Perform repeated matrix multiplications
(multiplication of input and weight matrices)
▪ Linear algebra libraries use optimized multiplication order internally
▪ Computer Graphics: 3D transformations involve chains of matrices for translation,
rotation, scaling
19
Matrix Chain Multiplication
▪ Step1: Optimal Substructure
20
Matrix Chain Multiplication
▪ Step2: Recursive Solution
21
Matrix Chain Multiplication
▪ Step3: Computing the optimal costs
22
Matrix Chain Multiplication
▪ Step4: Constructing an optimal solution
23
Matrix Chain Multiplication – Example
▪ Multiply the matrices A1, A2, A3, A4 with dimensions 5x10, 10x3, 3x12, 12x5
24
Optimal Binary Search Trees
▪ Given a sequence K = (k1, k2, …, kn) of n distinct keys in sorted order (so that k1 < k2
< < kn), and build a binary search tree from these keys.
▪ Optimal binary search tree: For a given set of probabilities (how often each key
occurs), construct a binary search tree whose expected search cost is smallest
(minimize the number of nodes visited in all the searches).
25
Optimal Binary Search Trees
▪ Minimizes expected search cost (number of comparisons)
▪ Considers access probabilities of keys
▪ Not about height balancing: An optimal binary search tree is not necessarily a tree
whose overall height is smallest
▪ Structure depends on probabilities, not height
▪ Frequency: Probability of occurrence of word
▪ High-probability keys are placed closer to the root
▪ Considers both successful searches and unsuccessful searches
▪ Problem: Construct an optimal BST so as to minimize the number of nodes visited in
all the searches, given that how often each word occurs
26
Optimal Binary Search Trees - Applications
▪ Compiler Design (Symbol Tables): Place frequently accessed symbols near the root –
reduces average lookup time during compilation
▪ Database Indexing: Frequently queried IDs placed closer to root
▪ Electronic Dictionary: Common words near the root
▪ Search Engine Autocomplete: High-probability queries (“weather”, “news”) near the
root
▪ Network Routing Tables: Frequently used (less traffic) network paths at smaller
depth
27
Optimal Binary Search Trees
▪ Number of possible BSTs for the given n:
28
Optimal Binary Search Trees
pi be the probability for search of ki
qi be the probability for search of di
29
Optimal Binary Search Trees using Dynamic Programming
▪ Step1: Structure of an OBST
30
Optimal Binary Search Trees using Dynamic Programming
▪ Step2: A recursive solution
▪ Goal is to compute e[1, n], expected cost of searching an optimal binary search tree
for all the actual and dummy keys.
▪ Let e[i, j] denote the expected cost of searching an optimal binary search tree
containing the keys ki,…,kj.
31
Optimal Binary Search Trees using Dynamic Programming
▪ Assume that the actual cost of a search equals the number of nodes examined
▪ Cost is depth at which the key occurs + 1
▪ Minimize the expected search cost
32
Optimal Binary Search Trees using Dynamic Programming
▪ Step2: A recursive solution
33
Optimal Binary Search Trees using Dynamic Programming
▪ Step3: Computing the expected search cost of an optimal binary search tree
34
Optimal Binary Search Trees – Example
▪ A set of n=5 keys with the following probabilities:
35