Dynamic Programming

Dynamic Programming
• An algorithm design technique (like divide and
conquer)

• Divide and conquer

– Partition the problem into independent subproblems

– Solve the subproblems recursively

– Combine the solutions to solve the original problem

2
 DP - Two key ingredients
• Two key ingredients for an optimization problem
to be suitable for a dynamic-programming
solution:

1. optimal substructures 2. overlapping subproblems

Subproblems are dependent.

Each substructure is (otherwise, a divide-and-
optimal. conquer approach is the
(Principle of optimality) choice.) 3
 Three basic components

• The development of a dynamic-programming

algorithm has three basic components:
– The recurrence relation (for defining the value of an
optimal solution);
– The tabular computation (for computing the value of
an optimal solution);
– The traceback (for delivering an optimal solution).

4
 Fibonacci numbers

The Fibonacci numbers are defined by the

following recurrence:

F =0
0
F =1
1
F = F − + F − for i>1 .
i i 1 i 2

5
How to compute F10？

F8
F9
F7 ……
F10
F7
F8
F6

6
 Dynamic Programming
• Applicable when subproblems are not independent
– Subproblems share subsubproblems
E.g.: Fibonacci numbers:
• Recurrence: F(n) = F(n-1) + F(n-2)
• Boundary conditions: F(1) = 0, F(2) = 1
• Compute: F(5) = 3, F(3) = 1, F(4) = 2
– A divide and conquer approach would repeatedly solve the
common subproblems
– Dynamic programming solves every subproblem just once and
stores the answer in a table

7
 Tabular computation
• The tabular computation can avoid
recompuation.

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10

0 1 1 2 3 5 8 13 21 34 55

Result

8
 Dynamic Programming Algorithm
1. Characterize the structure of an optimal
solution
2. Recursively define the value of an optimal
solution
3. Compute the value of an optimal solution in a
bottom-up fashion
4. Construct an optimal solution from computed
information

9
 The Knapsack Problem
• The 0-1 knapsack problem
– A thief robbing a store finds n items: the i-th item is
worth vi dollars and weights wi pounds (vi, wi integers)
– The thief can only carry W pounds in his knapsack
– Items must be taken entirely or left behind
– Which items should the thief take to maximize the
value of his load?
• The fractional knapsack problem
– Similar to above
– The thief can take fractions of items
10
 The 0-1 Knapsack Problem
• Thief has a knapsack of capacity W

• There are n items: for i-th item value vi and

weight wi

• Goal:
– find xi such that for all xi = {0, 1}, i = 1, 2, .., n

∑ wixi ≤ W and

∑ xivi is maximum

11
0-1 Knapsack - Dynamic Programming

• P(i, w) – the maximum profit that can be

obtained from items 1 to i, if the
knapsack has size w

• Case 1: thief takes item i

P(i, w) = vi + P(i - 1, w-wi)

• Case 2: thief does not take item i

P(i, w) = P(i - 1, w)

13
 0-1 Knapsack - Dynamic Programming
Item i was taken Item i was not taken

P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w ) }

Profit up to
Profit of remaining
prior item
capacity

0: 1 w - wi w W

0 0 0 0 0 0 0 0 0 0 0 0
0 first

0 second
i-1 0
i 0
0
n 0 14
Example:

Max Capacity, W = 5

Item Weight Value

1 2 12
2 1 10
3 3 20
4 2 15

15
 Max Capacity, W = 5 Item Weight Value
Example:
1 2 12
P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) }
2 1 10
w 3 3 20
0 1 2 3 4 5
4 2 15
0 0 0 0 0 0 0 P(1, 1) = P(~, 0) = 0 i wi vi

1 0 0 12 12 12 12 P(1, 2) = max{12+0, 0} = 12
i
2 0 10 12 22 22 22 P(1, 3) = max{12+0, 0} = 12
3 0 10 12 22 30 32 P(1, 4) = max{12+0, 0} = 12
4 0 10 15 25 30 37 P(1, 5) = max{12+0, 0} = 12

P(2, 1)= max{10+0, 0} = 10 P(3, 1)= P(2,1) = 10 P(4, 1)= P(3,1) = 10

P(2, 2)= max{10+0, 12} = 12 P(3, 2)= P(2,2) = 12 P(4, 2)= max{15+0, 12} = 15
P(2, 3)= max{10+12, 12} = 22 P(3, 3)= max{20+0, 22}=22 P(4, 3)= max{15+10, 22}=25
P(2, 4)= max{10+12, 12} = 22 P(3, 4)= max{20+10,22}=30 P(4, 4)= max{15+12, 30}=30
P(2, 5)= max{10+12, 12} = 22 P(3, 5)= max{20+12,22}=32 P(4, 5)= max{15+22, 32}=37
16
Reconstructing the Optimal Solution
0 1 2 3 4 5
0 0 0 0 0 0 0 • Item 4
1 0 0 12 12 12 12
• Item 2
2 0 10 12 22 22 22
3 0 10 12 22 30 32 • Item 1
4 0 10 15 25 30 37

Calculate w-wi
• Start at P(n, W)
• When you go left-up ⇒ item i has been taken
• When you go straight up ⇒ item i has not been
taken
17
Dynamic Programming
Coin Changing Problem
Introduction

● Problem 1: Find minimum number of coins to make a given amount.

● Problem 2: For above problem -> Which coins are selected?
● Problem 2: Find number of distinct ways to make a given amount.

● Why Dynamic Programming?

● • Greedy algorithms may fail.
● • DP explores all combinations efficiently.
1. Introduction

The Coin Change Problem is a classic dynamic programming problem. We're given a set
of coin denominations (e.g., [1, 2, 5]) and a total amount of money (e.g., 11).

The goal is to find the minimum number of coins required to make up that total amount.

● Example: For coins = [1, 2, 5] and amount = 11, the minimum number of coins is 3.
○ Solution: 5 + 5 + 1.
Why a "Greedy" Approach Doesn't Work

A simple, intuitive approach might be "greedy": always take the largest coin possible that is less than or equal to the remaining amount. Let's see
how this fails with a specific example.

● Coins: [1, 3, 4]
● Amount: 6

Greedy Approach:

1. Take the largest coin ≤ 6, which is 4.

2. Remaining amount is 6−4=2.
3. Take the largest coin ≤ 2, which is 1.
4. Remaining amount is 2−1=1.
5. Take the largest coin ≤ 1, which is 1.
6. Remaining amount is 1−1=0.

Total coins used: 3 (4 + 1 + 1).

Optimal Solution (found with Dynamic Programming):

● The correct solution is to use two coins: 3 + 3.

● Total coins used: 2.

Because the greedy approach failed to find the optimal solution, we need a more robust and systematic method, which is where dynamic
programming comes in.
2. Dynamic Programming Approach: The Logic
Dynamic programming solves problems by breaking them down into simpler, overlapping subproblems.
We build up a solution to the main problem by solving these smaller pieces first.

● We'll use a table (or array), let's call it dp, to store the minimum number of coins needed for
each amount from 0 up to our target amount.
● dp[i] will represent the minimum number of coins required to make the amount i.
● Our final answer will be dp[amount].
● We'll initialize dp[0] = 0 because it takes zero coins to make an amount of zero. All other dp
values will be initialized to a very large number (infinity) to represent that we haven't found a
solution yet.
3. The Recurrence Relation
The core of the dynamic programming solution is the recurrence relation. This formula tells us how to
calculate the value for each dp[i].

To find the minimum coins for an amount i, we can iterate through each coin denomination c we have.
If i >= c, we can potentially use coin c.

The recurrence relation is: dp[i]=min(dp[i],1+dp[i−c])

● dp[i]: The current minimum coins for amount i.

● 1 + dp[i - c]: Represents using one coin c plus the minimum number of coins needed for the
remaining amount (i - c).
● We take the minimum of these options to find the best solution for amount i.
4. Algorithm Step-by-Step
Let's walk through the algorithm with coins = [1, 2, 5] and amount = 11.

1. Initialize dp array: Create an array dp of size amount + 1 (12 elements).

○ dp[0] = 0.
○ dp[1...11] are initialized to infinity.
○ dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
2. Iterate through amounts: Loop from i = 1 to amount (11).
3. Iterate through coins: For each amount i, loop through all coin denominations c.
○ If i >= c: Update dp[i] using the recurrence relation: dp[i] = min(dp[i], 1 + dp[i - c])

The Table is shown next page

4. Final Answer: After the loops complete, dp[11] will hold the minimum number of coins. If dp[amount] is still
infinity, it means the amount cannot be made with the given coins.
Example

Total Amount: 10

Available Coins: 11 55 66 9
9

● We have to find minimum coins to make total amount.

 Total Amount: 10

Available Coins: 11 55 66 99

Amount 0 11 2 3 4 5 6 7 8 9 10

Min. 1 2
Coins
Needed

Amount to make = 2

Coin Choice = 11 + 1 =2

Remainder = 11
 Total Amount: 10

Available Coins: 11 55 66 99

Amount 0 11 2 3 4 5 6 7 8 9 10
Min. 1 2 3 4
Coins
Needed

Two Choice: [Choose the min]

1 5

Amount to make = 5 Amount to make = 5

Coin Choice = 1 +4 =5 Coin Choice = 5
5 +0 =1

Remainder = 44 Remainder = 0
 Total Amount: 10

Available Coins: 11 55 66 99

Amou 0 1 2 3 4 5 6 7 8 9 10
nt
Min. 1 2 3 4 1 1 2 3 1 2
Coins
Need
ed
Problem 2. How to Find – Which Coins are selected?

Total Amount: 10

Available Coins: 1 5 6 9

● While you select minimum number of coins, Which coins did you select?
 Total Amount: 10 Find- Min number of coins to make the total

Available Coins: 1 5 6 9

Total Amount, j

i coins 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0 0
Available Coins

1 1 0 1 2 3 4 5 6 7 8 9 10
2 5 0 1 2 3 4 1
3 6 0
4 9 0
Min (5, 1+0)
𝑰𝒇 𝒋 ≥ 𝒄𝒐𝒊𝒏𝒔[𝒊], 𝒅𝒑 𝒊 𝒋 = 𝐦𝐢𝐧( 𝒅𝒑 𝒊 − 𝟏 𝒋 , 𝟏 + 𝒅𝒑 [𝒊][𝒋 − 𝒄𝒐𝒊𝒏𝒔 𝒊 )

𝒆𝒍𝒔𝒆, 𝒅𝒑 𝒊 𝒋 = 𝒅𝒑 𝒊 − 𝟏 𝒋
 Total Amount: 10 Find- Min number of coins to make the total

Available Coins: 1 5 6 9

Total Amount

0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0
Available Coins

1 0 1 2 3 4 5 6 7 8 9 10
5 0 1 2 3 4 1 2 3 4 5 2
6 0 1 2 3 4 1 1 2 3 4 2
9 0 1 2 3 4 1 1 2 3 1 2
Coins Taken: 5 5 [ to make 10]

𝑰𝒇 𝒋 ≥ 𝒄𝒐𝒊𝒏𝒔[𝒊], 𝒅𝒑 𝒊 𝒋 = 𝐦𝐢𝐧( 𝒅𝒑 𝒊 − 𝟏 𝒋 , 𝟏 + 𝒅𝒑 [𝒊][𝒋 − 𝒄𝒐𝒊𝒏𝒔 𝒊 )

𝒆𝒍𝒔𝒆, 𝒅𝒑 𝒊 𝒋 = 𝒅𝒑 𝒊 − 𝟏 𝒋
Problem 3: Number of ways to get Total

Goal:
Coins: {1, 2, 5}
Given coins of certain denominations and a total amount, Total: 5
find how many distinct combinations of coins can sum
up to the total.
Ways:
•Input:
•coins[]: list of denominations 1. 1+1+1+1+1
•total: target amount 2. 1+1+1+2
3.1+2+2
•Output: Number of ways to make total 4.5

Example:
Coins = {1, 2, 5}, Total = 5 → 4 ways
Why Dynamic Programming?

● Brute force: Try all combinations → Exponential time

● DP: Break problem into overlapping subproblems
● Avoid recomputation using table or memoization
● Time complexity: O(n × total)
 Coins = {1, 2, 3}, Total = 5
Find- Number of ways to get Total

Total Amount, j

0 1 2 3 4 5
Available Coins, i

00 1 0 0 0 0 0

11 1 1 1 1 1 1

22 1 1 2

33 1 1 2

𝑰𝒇 𝒋 ≥ 𝒄𝒐𝒊𝒏𝒔 𝒊 , 𝒅𝒑 𝒊 𝒋 = 𝒅𝒑 𝒊 − 𝟏 𝒋 + 𝒅𝒑 [𝒊][𝒋 − 𝒄𝒐𝒊𝒏𝒔 𝒊 ]

𝒆𝒍𝒔𝒆, 𝒅𝒑 𝒊 𝒋 = 𝒅𝒑 𝒊 − 𝟏 𝒋
 Coins = {1, 2, 3}, Total = 5
Find- Number of ways to get Total

Total Amount

0 1 2 3 4 5
Available Coins

00 1 0 0 0 0 0

11 1 1 1 1 1 1

22 1 1 2 2 3 3

33 1 1 2 3 4 5

𝑰𝒇 𝒋 ≥ 𝒄𝒐𝒊𝒏𝒔 𝒊 , 𝒅𝒑 𝒊 𝒋 = 𝒅𝒑 𝒊 − 𝟏 𝒋 + 𝒅𝒑 [𝒊][𝒋 − 𝒄𝒐𝒊𝒏𝒔[𝒊]

𝒆𝒍𝒔𝒆, 𝒅𝒑 𝒊 𝒋 = 𝒅𝒑 𝒊 − 𝟏 𝒋
Dynamic Programming
Longest Common Subsequence (LCS)
Longest Common Subsequence (LCS)

• Application: comparison of two DNA strings

• Ex: X= {A B C B D A B }, Y= {B D C A B A}
• Longest Common Subsequence:
• X= AB C BDAB
• Y= BDCAB A
• Brute force algorithm would compare each
subsequence of X with the symbols in Y

39
 Longest Common Subsequence
• Given two sequences
X = x1, x2, …, xm
Y = y1, y2, …, yn
find a maximum length common subsequence
(LCS) of X and Y
• E.g.:
X = A, B, C, B, D, A, B
• Subsequences of X:
– A subset of elements in the sequence taken in order
A, B, D, B, C, D, B, etc.
40
 Example

X = A, B, C, B, D, A, B X = A, B, C, B, D, A, B

Y = B, D, C, A, B, A Y = B, D, C, A, B, A

• B, C, B, A and B, D, A, B are longest common

subsequences of X and Y (length = 4)

• B, C, A, however is not a LCS of X and Y

41
 Brute-Force Solution
• For every subsequence of X, check whether it’s a subsequence of
Y

• There are 2m subsequences of X to check

• Each subsequence takes (n) time to check

– scan Y for first letter, from there scan for second, and so on

• Running time: (n2m)

42
 LCS Algorithm

• First we’ll find the length of LCS. Later we’ll modify

the algorithm to find LCS itself.
• Define Xi, Yj to be the prefixes of X and Y of length i
and j respectively
• Define c[i,j] to be the length of LCS of Xi and Yj
• Then the length of LCS of X and Y will be c[m,n]

c[i − 1, j − 1] + 1 if x[i ] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise
43
 LCS recursive solution
c[i − 1, j − 1] + 1 if x[i ] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise
• We start with i = j = 0 (empty substrings of x and y)
• Since X0 and Y0 are empty strings, their LCS is
always empty (i.e. c[0,0] = 0)
• LCS of empty string and any other string is empty,
so for every i and j: c[0, j] = c[i,0] = 0

44
 LCS recursive solution
c[i − 1, j − 1] + 1 if x[i ] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise
• When we calculate c[i,j], we consider two cases:
• First case: x[i]=y[j]:
– one more symbol in strings X and Y matches, so the length
of LCS Xi and Yj equals to the length of LCS of smaller
strings Xi-1 and Yi-1 , plus 1

45
 LCS recursive solution

c[i − 1, j − 1] + 1 if x[i ] = y[ j ],
c[i, j ] = 
 max( c[i, j − 1], c[i − 1, j ]) otherwise
• Second case: x[i] != y[j]
– As symbols don’t match, our solution is not improved, and
the length of LCS(Xi , Yj) is the same as before (i.e.
maximum of LCS(Xi, Yj-1) and LCS(Xi-1,Yj)

Why not just take the length of LCS(Xi-1, Yj-1) ?

46
 LCS recursive solution

• Second case: i

j-1 j
x[i] != y[j]
i-1 i

47
3. Computing the Length of the LCS
0 if i = 0 or j = 0
c[i, j] = c[i-1, j-1] + 1 if xi = yj
max(c[i, j-1], c[i-1, j]) if xi  yj
0 1 2 n
yj: y1 y2 yn
0 xi 0 0 0 0 0 0
1 x1 0 first
2 x2 0 second
i
0
0
m xm 0
j
48
 Additional Information
0 if i,j = 0 A matrix b[i, j]:
c[i, j] = c[i-1, j-1] + 1 if xi = yj • For a subproblem [i, j] it
max(c[i, j-1], c[i-1, j]) if xi  yj tells us what choice was
made to obtain the
0 1 2 3 n
b & c: yj: A C D F optimal value
0 xi 0 0 0 0 0 0 • If xi = yj
1 A 0 b[i, j] = “ ”
2 B 0 • Else, if
c[i-1,j]
i c[i - 1, j] ≥ c[i, j-1]
3 C 0 c[i,j-1]
b[i, j] = “  ”
0
else
m D 0
b[i, j] = “  ”
j
49
 Additional Information
0 if i,j = 0 A matrix b[i, j]:
c[i, j] = c[i-1, j-1] + 1 if xi = yj • For a subproblem [i, j] it
max(c[i, j-1], c[i-1, j]) if xi  yj tells us what choice was
made to obtain the
0 1 2 3 4 n
b & c: yj: A C D E F optimal value
0 xi 0 0 0 0 0 0 • If xi = yj
1 A 0 b[i, j] = “ ”
2 B 0 • Else, if
i c[i - 1, j] ≥ c[i, j-1]
3 C 0 c[i-1,j-1]

b[i, j] = “  ”
4 E 0
else
m D 0
b[i, j] = “  ”
j
50
 LCS-LENGTH(X, Y, m, n)
1. for i ← 1 to m
2. do c[i, 0] ← 0 The length of the LCS if one of the sequences
3. for j ← 0 to n is empty is zero
4. do c[0, j] ← 0
5. for i ← 1 to m
6. do for j ← 1 to n
7. do if xi = yj
8. then c[i, j] ← c[i - 1, j - 1] + 1 Case 1: xi = yj
9. b[i, j ] ← “ ”
10. else if c[i - 1, j] ≥ c[i, j - 1]
11. then c[i, j] ← c[i - 1, j]
12. b[i, j] ← “↑” Case 2: xi  yj
13. else c[i, j] ← c[i, j - 1]
14. b[i, j] ← “←”
15. return c and b
Running time: (mn)
51
 Example
0 if i = 0 or j = 0
X = A, B, C, B, D, A
c[i, j] = c[i-1, j-1] + 1 if xi = yj
Y = B, D, C, A, B, A
max(c[i, j-1], c[i-1, j]) if xi  yj
0 1 2 3 4 5 6
If xi = yj yj B D C A B A
b[i, j] = “ ” 0 xi 0 0 0 0 0 0 0
1 A   
Else if 0 0 0 0 1 1 1
c[i - 1, j] ≥ c[i, j-1] 2 B 0 1 1 1

1 2 2
b[i, j] = “  ” 3 C 0

1

1 2 2

2

2
else 4 B 0 1

1

2

2 3 3
b[i, j] = “  ” 5 D 0

1 2

2

2

3

3
   
6 A 0 1 2 2 3 3 4
   
7 B 0 1 2 2 3 4 4
52
 4. Constructing a LCS
• Start at b[m, n] and follow the arrows
• When we encounter a “ “ in b[i, j]  xi = yj is an element
of the LCS
0 1 2 3 4 5 6
yj B D C A B A
0 xi 0 0 0 0 0 0 0
1 A   
0 0 0 0 1 1 1
2 B 
0 1 1 1 1 2 2
3 C    
0 1 1 2 2 2 2
4 B   
0 1 1 2 2 3 3
5 D     
0 1 2 2 2 3 3
   
6 A 0 1 2 2 3 3 4
   
7 B 0 1 2 2 3 4 4
53
 PRINT-LCS(b, X, i, j)
1. if i = 0 or j = 0 Running time: (m + n)
2. then return
3. if b[i, j] = “ ”
4. then PRINT-LCS(b, X, i - 1, j - 1)
5. print xi
6. elseif b[i, j] = “↑”
7. then PRINT-LCS(b, X, i - 1, j)
8. else PRINT-LCS(b, X, i, j - 1)

Initial call: PRINT-LCS(b, X, length[X], length[Y])

54
Longest Increasing
Subsequence (LIS)

57
Longest increasing subsequence(LIS)

• The longest increasing subsequence is to find

a longest increasing subsequence of a given
sequence of distinct integers a1a2…an .
e.g. 9 2 5 3 7 11 8 10 13 6
2 3 7
are increasing subsequences.
5 7 10 13
9 7 11 We want to find a longest one.
3 5 11 13 are not increasing subsequences.

58
 A naive approach for LIS
• Let L[i] be the length of a longest increasing
subsequence ending at position i.
L[i] = 1 + max j = 0..i-1{L[j] | aj < ai}
(use a dummy a0 = minimum, and L[0]=0)
Index 0 1 2 3 4 5 6 7 8 9 10

Input 0 9 2 5 3 7 11 8 10 13 6

Length

Prev

The subsequence 2, 3, 7, 8, 10, 13 is a

longest increasing subsequence.
This method runs in O(n2) time. 59
 A naive approach for LIS
• Let L[i] be the length of a longest increasing
subsequence ending at position i.
L[i] = 1 + max j = 0..i-1{L[j] | aj < ai}
(use a dummy a0 = minimum, and L[0]=0)
Index 0 1 2 3 4 5 6 7 8 9 10

Input 0 9 2 5 3 7 11 8 10 13 6

Length 0 1 1 2 2 3 4 4 5 6 3

Prev -1 0 0 2 2 4 5 5 7 8 4

The subsequence 2, 3, 7, 8, 10, 13 is a

longest increasing subsequence.
This method runs in O(n2) time. 60