Design & Analysis of Algorithms

CSE 304

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
optimal. divide-and-conquer approach
(Principle of optimality) is the 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
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.

10
 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

Path 1 1 1 1 1 2 2 2 2 2 2

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

longest increasing subsequence.
This method runs in O(n2) time. 11
 An O(n log n) method for LIS

• Define BestEnd[k] to be the smallest number

of an increasing subsequence of length k.
9 2 5 3 7 11 8 10 13 6
9 2 2 2 2 2 2 2 2 BestEnd[1]

5 3 3 3 3 3 3 BestEnd[2]

7 7 7 7 7 BestEnd[3]

11 8 8 8 BestEnd[4]

10 10 BestEnd[5]

13 BestEnd[6]

12
 An O(n log n) method for LIS

• Define BestEnd[k] to be the smallest number

of an increasing subsequence of length k.
9 2 5 3 7 11 8 10 13 6
9 2 2 2 2 2 2 2 2 2 BestEnd[1]

5 3 3 3 3 3 3 3 BestEnd[2]

7 7 7 7 7 6 BestEnd[3]

11 8 8 8 8 BestEnd[4]
For each position, we perform
a binary search to update 10 10 10 BestEnd[5]
BestEnd. Therefore, the
13 13 BestEnd[6]
running time is O(n log n).
13
 Sum of Subset Problem
• Problem:
– Suppose you are given N positive integer numbers
A[1…N] and it is required to produce another number
K using a subset of A[1..N] numbers. How can it be
done using Dynamic programming approach?
• Example:
N = 6, A[1..N] = {2, 5, 8, 12, 6, 14}, K = 19
Result: 2 + 5 + 12 = 19

14
 Coin Change Problem
• Suppose you are given n types of coin - C1, C2,
… , Cn coin, and another number K.
• Is it possible to make K using above types of
coin?
– Number of each coin is infinite
– Number of each coin is finite
• Find minimum number of coin that is required to
make K?
– Number of each coin is infinite
– Number of each coin is finite
 Maximum-sum interval
• Given a sequence of real numbers a1a2…an ,
find a consecutive subsequence with the
maximum sum.

9 –3 1 7 –15 2 3 –4 2 –7 6 –2 8 4 -9

For each position, we can compute the maximum-sum

interval starting at that position in O(n) time. Therefore, a
naive algorithm runs in O(n2) time.

Try Yourself
16
 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
17
 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

18
 0-1 Knapsack - Greedy Strategy
• E.g.:
3
Item 3 $120
0
5 5 5 +
Item 2 2
0 0 $100 0
3 0
Item 1 2 0 2
+ $100
1 0 1 0
$60
0 0
$60 $100 $120 $160 $220

$6/pound $5/pound $4/pound

• None of the solutions involving the greedy

choice (item 1) leads to an optimal solution
– The greedy choice property does not hold

19
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)
20
 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) }

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
21
 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
3 3 20
0 1 2 3 4 5
4 2 15
0 0 0 0 0 0 0 P(1, 1) = P(0, 1) = 0
1 0 0 12 12 12 12 P(1, 2) = max{12+0, 0} = 12
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
22
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

• 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
23
 Overlapping Subproblems
P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) }
0: 1 w W

0 0 0 0 0 0 0 0 0 0 0 0
0
0
i-1 0
i 0
0
n 0
E.g.: all the subproblems shown in grey may
depend on P(i-1, w)
24
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

25
 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.
26
 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

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

28
 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]

29
 LCS recursive solution

• 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

30
 LCS recursive solution

• 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

31
 LCS recursive solution

• 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) ?

32
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
33
 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 b[i, j] = “ ”
0
2 B • Else, if c[i - 1,
0 c[i-1,j]
i j] ≥ c[i, j-1]
3 C 0 c[i,j-1] b[i, j] = “ ↑ ”
0 else
m D 0 b[i, j] = “ ← ”
j
34
 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) 35
 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
↑ ↑ ↑
Else if c[i 1- 1,A 0 0 0 0 1 ←1 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
36
 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
37
 PRINT-LCS(b, X, i, j)
1. if i = 0 or j = 0 Running time: Θ(m +
2. then return n)

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

38
 Improving the Code
• If we only need the length of the LCS
– LCS-LENGTH works only on two rows of c at a time

• The row being computed and the previous row

– We can reduce the asymptotic space requirements by
storing only these two rows

39
 LCS Algorithm Running Time

• LCS algorithm calculates the values of each entry of

the array c[m,n]
• So what is the running time?

O(m*n)
since each c[i,j] is calculated in constant
time, and there are m*n elements in the
array

40
 Rock Climbing Problem

• A rock climber wants to get

from the bottom of a rock to
the top by the safest possible
path.

• At every step, he reaches for

handholds above him; some
holds are safer than other.

• From every place, he can only

reach a few nearest
handholds.
 Rock climbing (cont)

❖Suppose we have a wall

instead of the rock. 4
5 3
2
At every step our climber can reach exactly three
handholds: above, above and to the right and
above and to the left.

There is a table of “danger ratings” provided. The

“Danger” of a path is the sum of danger ratings of
all handholds on the path.
 Rock Climbing (cont)
•We represent the wall as a 22 8 9 55 8
table.
4 44 6 22 3
•Every cell of the table contains 5 7 5 6 11
the danger rating of the 3 22 5 44 8
corresponding block.
The obvious greedy algorithm does not give an
optimal solution.The rating of this path is 13.
The rating of an optimal path is 12.
However, we can solve this problem by a
dynamic programming strategy in polynomial
time.
Idea: once we know the rating of a path to
every handhold on a layer, we can easily
compute the ratings of the paths to the
holds on the next layer.

For the top layer, that gives us an

answer to the problem itself.
For every handhold, there is only one
“path” rating. Once we have reached a
hold, we don’t need to know how we got
there to move to the next level.

This is called an “optimal substructure” property.

Once we know optimal solutions to
subproblems, we can compute an optimal
solution to the problem itself.
Recursive solution:

To find the best way to get to stone j in row

i, check the cost of getting to the stones
• (i-1,j-1),
• (i-1,j) and
• (i-1,j+1), and take the cheapest.

Problem: each recursion level makes three

calls for itself, making a total of 3n calls –
too much!
Solution - memorization

We query the value of A(i,j) over and over

again.
Instead of computing it each time, we can
compute it once, and remember the value.

A simple recurrence allows us to compute

A(i,j) from values below.
 Dynamic programming

• Step 1: Describe an array of values you want

to compute.

• Step 2: Give a recurrence for computing later

values from earlier (bottom-up).

• Step 3: Give a high-level program.

• Step 4: Show how to use values in the array

to compute an optimal solution.
 Rock climbing: step 1.

• Step 1: Describe an array of values you want

to compute.

• For 1 ≤ i ≤ n and 1 ≤ j ≤ m, define A(i,j) to be

the cumulative rating of the least dangerous
path from the bottom to the hold (i,j).

• The rating of the best path to the top will be

the minimal value in the last row of the array.
 Rock climbing: step 2.
• Step 2: Give a recurrence for computing later values from
earlier (bottom-up).

• Let C(i,j) be the rating of the hold (i,j). There are three
cases for A(i,j):

• Left (j=1): C(i,j)+min{A(i-1,j),A(i-1,j+1)}

• Right (j=m): C(i,j)+min{A(i-1,j-1),A(i-1,j)}

• Middle: C(i,j)+min{A(i-1,j-1),A(i-1,j),A(i-1,j+1)}

• For the first row (i=1), A(i,j)=C(i,j).

 Rock climbing: simpler step 2

• Add initialization row: A(0,j)=0. No danger to

stand on the ground.

• Add two initialization columns:

A(i,0)=A(i,m+1)=∞. It is infinitely dangerous to
try to hold on to the air where the wall ends.

• Now the recurrence becomes, for every i,j:

A(i,j) = C(i,j)+min{A(i-1,j-1),A(i-1,j),A(i-1,j+1)}
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ ∞
2 8 9 5 8 2 ∞ ∞
3 ∞ ∞
4 ∞ ∞

Initialization: A(i,0)=A(i,m+1)=∞,
A(0,j)=0
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ ∞
3 ∞ ∞
4 ∞ ∞

The values in the first row are the same as

C(i,j).
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 ∞
3 ∞ ∞
4 ∞ ∞

A(2,1)=5+min{∞,3,2}=7
.
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 ∞
3 ∞ ∞
4 ∞ ∞

A(2,1)=5+min{∞,3,2}=7.
A(2,2)=7+min{3,2,5}=9
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 7 ∞
3 ∞ ∞
4 ∞ ∞

A(2,1)=5+min{∞,3,2}=7.
A(2,2)=7+min{3,2,5}=9
A(2,3)=5+min{2,5,4}=7.
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 7 10 5 ∞
3 ∞ ∞
4 ∞ ∞

The best cumulative rating on the second

row is 5.
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 7 10 5 ∞
3 ∞ 11 11 13 7 8 ∞
4 ∞ ∞

The best cumulative rating on the third row

is 7.
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 7 10 5 ∞
3 ∞ 11 11 13 7 8 ∞
4 ∞ 13 19 16 12 15 ∞

The best cumulative rating on the last row

is 12.
 Rock climbing: example
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 7 10 5 ∞
3 ∞ 11 11 13 7 8 ∞
4 ∞ 13 19 16 12 15 ∞

The best cumulative rating on the last row

is 12.
So the rating of the best path to the top
is 12.
 Rock climbing example: step 4
C(i,j): A(i,j):

3 2 5 4 8 i\j 0 1 2 3 4 5 6
5 7 5 6 1 0 ∞ 0 0 0 0 0 ∞
4 4 6 2 3 1 ∞ 3 2 5 4 8 ∞
2 8 9 5 8 2 ∞ 7 9 7 10 5 ∞
3 ∞ 11 11 13 7 8 ∞
4 ∞ 13 19 16 12 15 ∞

To find the actual path we need to retrace backwards

the decisions made during the calculation of A(i,j).
 Rock climbing example: step 4
C(i,j): A(i,j):
i\j 0 1 2 3 4 5 6
3 2 5 4 8
0 ∞ 0 0 0 0 0 ∞
5 7 5 6 1
1 ∞ 3 2 5 4 8 ∞
4 4 6 2 3
2 ∞ 7 9 7 10 5 ∞
2 8 9 5 8
3 ∞ 11 11 13 7 8 ∞
The last hold was (4,4). 4 ∞ 13 19 16 12 15 ∞

To find the actual path we need to retrace backwards

the decisions made during the calculation of A(i,j).
 Rock climbing example: step 4
C(i,j): A(i,j):
i\j 0 1 2 3 4 5 6
3 2 5 4 8
0 ∞ 0 0 0 0 0 ∞
5 7 5 6 1
1 ∞ 3 2 5 4 8 ∞
4 4 6 2 3
2 ∞ 7 9 7 10 5 ∞
2 8 9 5 8
3 ∞ 11 11 13 7 8 ∞
The hold before the last 4 ∞ 13 19 16 12 15 ∞
was (3,4), since
min{13,7,8} was 7.

To find the actual path we need to retrace backwards

the decisions made during the calculation of A(i,j).
 Rock climbing example: step 4
C(i,j): A(i,j):
i\j 0 1 2 3 4 5 6
3 2 5 4 8
0 ∞ 0 0 0 0 0 ∞
5 7 5 6 1
1 ∞ 3 2 5 4 8 ∞
4 4 6 2 3
2 ∞ 7 9 7 10 5 ∞
2 8 9 5 8
3 ∞ 11 11 13 7 8 ∞
The hold before that 4 ∞ 13 19 16 12 15 ∞
was (2,5), since
min{7,10,5} was 5.

To find the actual path we need to retrace backwards

the decisions made during the calculation of A(i,j).
 Rock climbing example: step 4
C(i,j): A(i,j):
i\j 0 1 2 3 4 5 6
3 2 5 4 8
0 ∞ 0 0 0 0 0 ∞
5 7 5 6 1
1 ∞ 3 2 5 4 8 ∞
4 4 6 2 3
2 ∞ 7 9 7 10 5 ∞
2 8 9 5 8
3 ∞ 11 11 13 7 8 ∞
Finally, the first hold 4 ∞ 13 19 16 12 15 ∞
was (1,4), since
min{5,4,8} was 4.

To find the actual path we need to retrace backwards

the decisions made during the calculation of A(i,j).
 Rock climbing example: step 4
C(i,j): A(i,j):
i\j 0 1 2 3 4 5 6
3 2 5 4 8
0 ∞ 0 0 0 0 0 ∞
5 7 5 6 1
1 ∞ 3 2 5 4 8 ∞
4 4 6 2 3
2 ∞ 7 9 7 10 5 ∞
2 8 9 5 8
3 ∞ 11 11 13 7 8 ∞
4 ∞ 13 19 16 12 15 ∞

We are done!
 Printing out the solution recursively
PrintBest(A,i,j) // Printing the best path ending at (i,j)
if (i==0) OR (j=0) OR (j=m+1)
return;
if (A[i-1,j-1]<=A[i-1,j]) AND (A[i-1,j-1]<=A[i-1,j+1])
PrintBest(A,i-1,j-1);
elseif (A[i-1,j]<=A[i-1,j-1]) AND (A[i-1,j]<=A[i-1,j+1])
PrintBest(A,i-1,j);
elseif (A[i-1,j+1]<=A[i-1,j-1]) AND (A[i-1,j+1]<=A[i-1,j])
PrintBest(A,i-1,j+1);
printf(i,j)