Dynamic Programming

1
What is Dynamic Programming?
• Dynamic programming is a very powerful, general tool for solving
optimization problems.
• Once understood it is relatively easy to apply, but many people have
trouble understanding it.
• Why not Greedy?
• Greedy algorithms focus on making the best local choice at each decision
point.
• For example, a natural way to compute a shortest path from x to y might be to
walk out of x, repeatedly following the cheapest edge until we get to y.
WRONG!
• In the absence of a correctness proof, greedy algorithms are very likely to fail.

2
Example 1 – Fibonacci number generation
Problem:
Let’s consider the calculation of Fibonacci numbers:

F(n) = F(n-2) + F(n-1)

with seed values F(1) = 1, F(2) = 1

or F(0) = 0, F(1) = 1

What would a series look like:

0, 1, 1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89, 144, …

3
Example 1 – Fibonacci number generation
Recursive Algorithm:

Fib(n)
{
if (n == 0)
return 0;

if (n == 1)
return 1;

Return Fib(n-1)+Fib(n-2)
}
4
Example 1 – Fibonacci number generation
Recursive Algorithm:

Fib(n) It has a serious issue!

{
if (n == 0)
return 0;

if (n == 1)
return 1;

Return Fib(n-1)+Fib(n-2)
}
5
Example 1 – Fibonacci number generation
Recursion tree
What’s the problem?

6
Example 1 – Fibonacci number generation
Memoization:
Fib(n)
{
if (n == 0)
return M[0];
if (n == 1)
return M[1];
if (Fib(n-2) is not calculated)
call Fib(n-2);
if(Fib(n-1) is not calculated)
call Fib(n-1);
//Store the ${n}^{th}$ Fibonacci no. in memory & use previous results.
M[n] = M[n-1] + M[n-2]
Return M[n];
}
7
Example 1 – Fibonacci number generation

already calculated …

8
Dynamic programming - Approach
- Main approach: recursive, holds answers to a sub problem in
a table, can be used without recomputing.

- Can be formulated both via recursion and saving results in a

table (memoization). Typically, we first formulate the
recursive solution and then turn it into recursion plus
dynamic programming via memoization or bottom-up.

- ”programming” as in tabular not programming code

9
Elements of Dynamic Programming
• Optimal Substructure
• An optimal solution to a problem contains within it an optimal
solution to subproblems
• Optimal solution to the entire problem is build in a bottom-up
manner from optimal solutions to subproblems
• Overlapping Subproblems
• If a recursive algorithm revisits the same subproblems over and
over  the problem has overlapping subproblems
10
0-1 Knapsack – DP approach

11
0-1 Knapsack – Algorithm
for w=0 to W do
B[w] = 0
for k=1 to n do
{ k=W
for j=W downto wk do for i = n downto 1 do
{ {
if B[j-wk]+bk > B[j] if keep[i, k] == 1
{ B[j]= B[j-wk]+bk {
keep[k, j] = 1 output i “as selected”
} k = k-wi
else }
keep[k, j] = 0 }
}
} 12
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.

• Initialize the benefit array

• Initialize the keep array
• Solve using DP approach

13
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.
B[0] 0
B[1] 0
B[2] 0 0 1 2 3 4 5 6 7 8 9 10

B[3] 0 1

B[4] 0 2

B[5] 0 3

B[6] 0 4

B[7] 0
B[8] 0 Initialize the Keep array
B[9] 0 Initialize the
B[10] 0 Benefit array 14
0-1 Knapsack – Algorithm
for w=0 to W do
B[w] = 0
for k=1 to n do
{ k=W
for j=W downto wk do for i = n downto 1 do
{ {
if B[j-wk]+bk > B[j] if keep[i, k] == 1
{ B[j]= B[j-wk]+bk {
keep[k, j] = 1 output i “as selected”
} k = k-wi
else }
keep[k, j] = 0 }
}
} 15
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.
B[0] 0
B[1] 0
B[2] 0 0 1 2 3 4 5 6 7 8 9 10

B[3] 0 1

B[4] 0 2

B[5] 0 3

B[6] 0 4

B[7] 0
B[8] 0 Initialize the Keep array
B[9] 0 Initialize the
B[10] 0 Benefit array 16
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.
B[0] 0
B[1] 0
B[2] 0 0 1 2 3 4 5 6 7 8 9 10

B[3] 0 1 1 1 1 1 1 1

B[4] 0 2

B[5] 0 10 3

B[6] 0 10 4

B[7] 0 10
B[8] 0 10 Keep array
B[9] 0 10
B[10] 0 10 17
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.
B[0] 0
B[1] 0
B[2] 0 0 1 2 3 4 5 6 7 8 9 10

B[3] 0 1 1 1 1 1 1 1

B[4] 0 40 2 1 1 1 1 1 1 1

B[5] 0 10 40 3

B[6] 0 10 40 4

B[7] 0 10 40
B[8] 0 10 40 Keep array
B[9] 0 10 50
B[10] 0 10 50 18
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.
B[0] 0
B[1] 0
B[2] 0 0 1 2 3 4 5 6 7 8 9 10

B[3] 0 1 1 1 1 1 1 1

B[4] 0 40 2 1 1 1 1 1 1 1

B[5] 0 10 40 3 0 0 0 0 1

B[6] 0 10 40 4

B[7] 0 10 40
B[8] 0 10 40 Keep array
B[9] 0 10 50
B[10] 0 10 50 70 19
0-1 Knapsack – Example 1
• Find the solution for the 0-1 knapsack problem with benefit-weight
pairs as (10, 5), (40, 4), (30, 6), (50, 3) and total sack capacity as 10.
B[0] 0
B[1] 0
B[2] 0 0 1 2 3 4 5 6 7 8 9 10

B[3] 0 50 1 1 1 1 1 1 1

B[4] 0 40 50 2 1 1 1 1 1 1 1

B[5] 0 10 40 50 3 0 0 0 0 1

B[6] 0 10 40 50 4 1 1 1 1 1 1 1 1

B[7] 0 10 40 90
B[8] 0 10 40 90 Keep array
B[9] 0 10 50 90
B[10] 0 10 50 70 90 Maximum Profit 20
0-1 Knapsack – Algorithm
for w=0 to W do
B[w] = 0
for k=1 to n do
{ k=W
for j=W downto wk do for i = n downto 1 do
{ {
if B[j-wk]+bk > B[j] if keep[i, k] == 1
{ B[j]= B[j-wk]+bk {
keep[k, j] = 1 output i “as selected”
} k = k-wi
else }
keep[k, j] = 0 }
}
} 21
0-1 Knapsack – Example 1 I1 - (10, 5),
0 1 2 3 4 5 6 7 8 9 10 I2 - (40, 4),
1 1 1 1 1 1 1
2 1 1 1 1 1 1 1
I3 - (30, 6),
3 0 0 0 0 1 I4 - (50, 3)
4 1 1 1 1 1 1 1 1

k=10
i=4 to 1
When i=4, keep[4,10]==1??
Yes, pick item 4, k=10-3 = 7
When i=3, keep[3,7]==1?? Final Solution,
No [0, 1, 0, 1] = 90
When i=2, keep[2,7]==1??
Yes, pick item 2, k=7-4 = 3
When i=1, keep[1,3]==1?? No 22
0-1 Knapsack – Algorithm
for w=0 to W do
B[w] = 0
for k=1 to n do
{ k=W
for j=W downto wk do for i = n downto 1 do
{ {
if B[j-wk]+bk > B[j] if keep[i, k] == 1
{ B[j]= B[j-wk]+bk {
keep[k, j] = 1 output i “as selected”
} k = k-wi
else }
keep[k, j] = 0 }
} Complexity?? O(nW)
} 23
0-1 Knapsack – Example 2
• Consider the given benefit-weight list for four items as {1, 4, 5, 7} and
{1, 3, 4, 5}. Solve the 0-1 knapsack problem assuming W=7.

B[0] 0 0 1 2 3 4 5 6 7
B[1] 0 1
B[2] 0 2
B[3] 0 3
B[4] 0 4
B[5] 0
B[6] 0 Keep array
B[7] 0
Benefit array
24
0-1 Knapsack – Example 2
• Consider the given benefit-weight list for four items as {1, 4, 5, 7} and {1, 3,
4, 5} respectively. Solve the 0-1 knapsack problem assuming W=7.

B[0] 0 0 1 2 3 4 5 6 7
B[1] 0 1 1 1 1 1 1 1 1 1
B[2] 0 1 2
B[3] 0 1 3
B[4] 0 1 4
B[5] 0 1
B[6] 0 1 Keep array
B[7] 0 1
Benefit array
25
0-1 Knapsack – Example 2
• Consider the given benefit-weight list for four items as {1, 4, 5, 7} and {1, 3,
4, 5} respectively. Solve the 0-1 knapsack problem assuming W=7.

B[0] 0 0 1 2 3 4 5 6 7
B[1] 0 1 1 1 1 1 1 1 1 1
B[2] 0 1 2 1 1 1 1 1
B[3] 0 1 4 3
B[4] 0 1 5 4
B[5] 0 1 5
B[6] 0 1 5 Keep array
B[7] 0 1 5
Benefit array
26
0-1 Knapsack – Example 2
• Consider the given benefit-weight list for four items as {1, 4, 5, 7} and {1, 3,
4, 5} respectively. Solve the 0-1 knapsack problem assuming W=7.

B[0] 0 0 1 2 3 4 5 6 7
B[1] 0 1 1 1 1 1 1 1 1 1
B[2] 0 1 2 1 1 1 1 1
B[3] 0 1 4 3 0 1 1 1
B[4] 0 1 5 4
B[5] 0 1 5 6
B[6] 0 1 5 6 Keep array
B[7] 0 1 5 9
Benefit array
27
0-1 Knapsack – Example 2
• Consider the given benefit-weight list for four items as {1, 4, 5, 7} and {1, 3,
4, 5} respectively. Solve the 0-1 knapsack problem assuming W=7.

B[0] 0 0 1 2 3 4 5 6 7
B[1] 0 1 1 1 1 1 1 1 1 1
B[2] 0 1 2 1 1 1 1 1
B[3] 0 1 4 3 0 1 1 1
B[4] 0 1 5 4 1 1 0
B[5] 0 1 5 6 7
B[6] 0 1 5 6 8 Keep array
B[7] 0 1 5 9 Maximum Profit
Benefit array 28
0-1 Knapsack – Example 1 I1 - (1, 1),
0 1 2 3 4 5 6 7 I2 - (4, 3),
1 1 1 1 1 1 1 1 I3 - (5, 4),
2 1 1 1 1 1
3 0 1 1 1
I4 - (7, 5)
4 1 1 0
k=7
i=4 to 1
When i=4, keep[4,7]==1??
No
When i=3, keep[3,7]==1?? Final Solution,
Yes, pick item 3, k=7-4 = 3 [0, 1, 1, 0] = 9
When i=2, keep[2,3]==1??
Yes, pick item 2, k=3-3 = 0
When i=1, keep[1,0]==1?? No 29
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.

30
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

31
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)

32
Making the choice
Scenario 1
X = A, B, D, E
Y = Z, B, E
• Choice: include one element into the common sequence (E) and solve the
resulting subproblem
Scenario 2
X = A, B, D, G
Y = Z, B, D
• Choice: exclude an element from a string and solve the resulting
subproblem
33
Notations

• Given a sequence X = x1, x2, …, xm we define the i-th prefix of X, for i
= 0, 1, 2, …, m

Xi = x1, x2, …, xi

• c[i, j] = the length of a LCS of the sequences Xi = x1, x2, …, xi and
Yj = y1, y2, …, yj
34
A Recursive Solution
Case 1: xi = yj
e.g.: Xi = A, B, D, E
Yj = Z, B, E
c[i, j] = c[i - 1, j - 1] + 1

• Append xi = yj to the LCS of Xi-1 and Yj-1

• Must find a LCS of Xi-1 and Yj-1  optimal solution to a problem includes
optimal solutions to subproblems

35
A Recursive Solution
Case 2: xi  yj
e.g.: Xi = A, B, D, G
Yj = Z, B, D
c[i, j] = max { c[i - 1, j], c[i, j-1] }
• Must solve two problems
• find a LCS of Xi-1 and Yj: Xi-1 = A, B, D and Yj = Z, B, D
• find a LCS of Xi and Yj-1: Xi = A, B, D, G and Yj = Z, B

• Optimal solution to a problem includes optimal solutions

to subproblems 36
Overlapping Subproblems

• To find a LCS of X and Y

• we may need to find the LCS between X and Yn-1 and that of Xm-1 and Y

• Both the above subproblems has the subproblem of finding the LCS of Xm-1

and Yn-1

• Subproblems share subsubproblems

37
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
38
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
b[i, j] = “  ”
c[i,j-1]

0
else
m D 0
b[i, j] = “  ”
j
39
LCS-LENGTH(X, Y, m, n)
1. for i ← 1 to m
The length of the LCS if one of the sequences
2. do c[i, 0] ← 0
is empty is zero
3. for j ← 0 to n
4. do c[0, j] ← 0
5. for i ← 1 to m
6. do for j ← 1 to n
7. do if xi = yj Case 1: xi = yj
8. then c[i, j] ← c[i - 1, j - 1] + 1
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] ← “↑”
13. else c[i, j] ← c[i, j - 1] Case 2: xi  yj
14. b[i, j] ← “←”
15. return c and b

Running time: (mn)

40
Example 1 0 if i = 0 or j = 0
X = A, B, C, B, D, A, B
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
41
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 Solution:
5 D     
0 1 2 2 2 3 3 BCBA
   
6 A 0 1 2 2 3 3 4
   
7 B 0 1 2 2 3 4 4
42
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])

43
Example 2
• X = ABCABA Y = BACBCA

X/Y 0 1 2 3 4 5 6
Yi B A C B C A
0 Xi 0 0 0 0 0 0 0
1 A 0 0 1 1 1 1 1
2 B 0 1 1 1 2 2 2 Solution:
3 C 0 1 1 2 2 3 3 ABCA
4 A 0 1 2 2 2 3 4
5 B 0 1 2 2 3 3 4
6 A 0 1 2 2 3 3 4

44