COMP3121/9101/3821/9801
Lecture Notes
More on Dynamic Programming (DP)
LiC: Aleks Ignjatovic
THE UNIVERSITY OF
NEW SOUTH WALES
School of Computer Science and Engineering
The University of New South Wales
Sydney 2052, Australia
1 Turtle Tower
You are given n turtles, and for each turtle you are given its weight and its
strength. The strength of a turtle is the maximal weight you can put on it
without cracking its shell. Find the largest possible number of turtles which
you can stack one on top of the other without cracking any turtle. (Hint: for
each turtle consider the sum of its weight and its strength.)
Solution
This problem illustrates well several important steps involved in applying DP.
Let the turtles be denoted by T1, . . . , Tn where the turtles are in an arbitrary
order, and let the weight of turtle Ti be W (Ti) and its strength S(Ti). We will
say that a tower of turtles is legitimate if the strength of each turtle in the tower
is larger or equal to the weight of all turtles placed on top of it.
Generalizing the problem. DP involves building a solution of a problem
recursively from solutions of its subproblems. Thus, instead of solving just
the problem itself, we solve a whole set of its subproblems. For example, in
this problem we might want to solve all of the following subproblems for all
1 ≤ j ≤ n:
Subproblem P(j): Find the largest possible number of turtles from the set
{T1, . . . , Tj} which you can stack one on top of the other without cracking any
turtle.
We might now try to build a solution to P (j) by extending an optimal so-
lution to a problem {P (i) : 1 ≤ i < j} if possible. However, a longest chain
built by choosing from turtles {Ti : 1 ≤ i ≤ j} and which includes Tj might
contain turtle Tj NOT as the last turtle in the tower but somewhere in the
middle. Thus, such chain is not an extension of an optimal chain for any of the
sub problems {P (i) : 1 ≤ i < j} because solutions to such problems are built
from turtles with indices strictly smaller than i.
Choosing the right ordering. Thus, we have to find a proper set of subprob-
lems together with an appropriate ordering on such subproblems which allows
a recursive construction and which does not miss all optimal solutions, i.e., so
that at least one optimal solution can be obtained by such a recursion. In
this particular problem finding such ordering is tricky: one should order tur-
tles according to the sum of their weight and their strength, in an increasing way.
Claim: If there exists a legitimate tower of height k, then there must also exist
a tower of height k which is non-decreasing with respect to weight plus strength
of a turtle, i.e. if there is a legitimate tower of turtles of height m there must
be a tower 〈t1, . . . , tm〉 of the same height such that
i < j ⇒W (ti) + S(ti) ≤W (tj) + S(tj). (1.1)
1
To prove this claim we will show that in fact any legitimate tower of turtles
can be reordered into another legitimate tower of turtles which is non-decreasing
with respect to the weight plus strength of turtles. Thus, let 〈t1, . . . , tm〉 be any
legitimate tower; it is enough to show that if two consecutive turtles ti and ti+1
in that tower satisfy
W (ti+1) + S(ti+1) < W (ti) + S(ti), (1.2)
then these two turtles ti and ti+1 can be swapped and still obtain a legitimate
tower. If we prove this, we can then use the BubbleSort algorithm to get the
whole tower into a non-decreasing order of weight plus strength of each turtle.
So the original tower τ and the new tower τ∗ obtained by swapping ti and
ti+1 look like this:
τ =〈t1, . . . ti−1, ti, ti+1, ti+2 . . . , tm〉
τ∗ =〈t1, . . . ti−1, ti+1, ti, ti+2, . . . , tm〉
The only turtle which has more weight on its back in the new tower τ∗ than it
had in the (legitimate) tower τ is turtle ti; thus, it is enough to show that the
weight on its back is smaller than its strength, i.e., that
i−1∑
j=1
W (tj) +W (ti+1) < S(ti) (1.3)
Since the original tower was legitimate, we have
i−1∑
j=1
W (tj) +W (ti) ≤ S(ti+1)
Adding W (ti+1) to both sides of this inequality we get
i−1∑
j=1
W (tj) +W (ti) +W (ti+1) ≤W (ti+1) + S(ti+1) (1.4)
However, we assumed that W (ti+1) + S(ti+1) < W (ti) + S(ti); see (1.2), thus
by combining this with (1.4) we get
i−1∑
j=1
W (tj) +W (ti) +W (ti+1) ≤W (ti+1) + S(ti+1) < W (ti) + S(ti). (1.5)
We can now cancel out W (ti) which appears on both sides of
i−1∑
j=1
W (tj) +W (ti) +W (ti+1) < W (ti) + S(ti), (1.6)
2
and obtain
i−1∑
j=1
W (tj) +W (ti+1) < S(ti), (1.7)
which is precisely what we had to prove; see (1.3).
The above claim has the following important consequence: we can restrict
ourselves to non-decreasing towers and still obtain an optimal solution.
Thus, we order turtles according to the sum of their strength plus their
weight, i.e., assume that for all i, j ≤ n
i < j ⇒W (Ti) + S(Ti) ≤W (Tj) + S(Tj), (1.8)
and proceed by recursion along such an ordering.
Let us now first try to solve the problem using the trick which we have used
before: for every i ≤ n we try to look for the tallest non-decreasing tower of
turtles which ends with turtle Ti.
However, there is a problem: let 〈t1, . . . tm, Ti〉 be the tallest legitimate
tower ending with Ti and with {t1, . . . tm−1, tm} ⊆ {T1, . . . , Ti−1}. Unfortu-
nately, the tower 〈t1, . . . , tm−1, tm〉 might not be the tallest possible tower end-
ing with turtle tm; there might be a legitimate tower with at least m+ 1 turtles
〈t∗1, . . . , t∗m, tm〉 which ends with tm, but such tower could be too heavy to put
on top of Ti, i.e., tower 〈t∗1, . . . , t∗m, tm, Ti〉 might crack turtle Ti. Thus, an op-
timal tower for Ti might not be obtained by extending an optimal tower for Tj
for some j < i. We need to generalise our problem more carefully to have the
optimal substructure, i.e., to be able to build new optimal solutions from the
previous ones.
To guarantee that optimal towers can be obtained from the previous optimal
towers, for every i ≤ n we build a sequence of lightest possible towers of
every possible height, built from turtles 〈T1, . . . Ti−1, Ti〉.
Thus, we solve the following generalisations of our problem, for every j ≤ n:
Subproblem P(j): For each k ≤ j for which there exists a tower of turtles of
length k built from turtles {T1, . . . , Tj} (not necessarily containing Tj), find the
lightest one.
Now the recursion works: assume that we have solved subproblem P (i− 1).
To obtain the lightest tower θik of any length k built from turtles {T1, . . . , Ti}
we look at the lightest tower θi−1k of length k and the lightest tower θ
i−1
k−1 of
length k − 1, both built from turtles T1, T2, . . . , Ti−1. If the tower obtained by
extending θi−1k−1 with Ti is both legitimate and lighter than θ
i−1
k we let θ
i
k be
such a tower; otherwise we let θik = θ
i−1
k . This produces an optimal solution
because if it is possible at all to place a tower of length l on top of a turtle, then
it is certainly possible to place the lightest tower of length l on top of this turtle.
Also, if the highest tower built from turtles T1, T2, . . . , Ti−1 is of height m and
Ti can extend it, we get the first possible legitimate tower of height m+ 1 built
from turtles T1, T2, . . . , Ti−1, Ti.
3
The solution to our problem is now obtained from the solution to P (n) by
picking the longest tower obtained by solving P (n).
Exercise: Use a similar reasoning to solve the following problem: Given a
sequence of n numbers find the longest increasing subsequence in nlog n steps.
2 Minimizing Total Variation of a Sequence
The total variation V (s) of a sequence of numbers s = 〈x1, x2, . . . , xk〉 is defined
as follows: if s has only one element, i.e., if k = 1, then V (s) = 0; if k > 1 then
V (s) =
k−1∑
i=1
|xi+1 − xi|.
Assume that you are given a sequence of n numbers a1, a2, . . . an. Split such a
sequence into two subsequences (preserving the ordering of elements) such that
the sum of total variations of the two sequences is as small as possible, i.e., find
subsequences σ1, σ2 such that
σ1 = 〈xi1 , . . . xik〉; i1 < i2 < . . . < ik
σ2 = 〈xj1 , . . . xjn−k〉; j1 < j2 < . . . < jn−k
{i1, i2, . . . , ik} ∪ {j1, j2, . . . , jn−k} = {1, 2, 3, . . . , n}
and such that V (σ1) + V (σ2) is as small as possible.
Solution: This is another tricky one. One might be tempted to reason as
follows. Let us try to solve recursively the following subproblems for all m ≤ n:
Subproblem P(j): Split the subsequence s = 〈a1, a2, . . . , am〉 into two sequences
such that the sum of their total variations is minimal.
Assume that we have an optimal solution for the sequence s = 〈a1, a2, . . . , am〉
and that a such solution results in two subsequences, s1 = 〈x1, x2, . . . , xk〉 whose
4
last element is xk for some k < m and a sequence s2 = 〈y1, y2, . . . , ym−k〉 whose
last element is ym−k = am; see Figure 2.1 (top).
a1 a2 a3 a4 a5 a6 . . . am-2 am-1 am am+1
X1 y1 y2 X2 X3 y3 y4 X4 Xk ym-k
If |Xk - am+1| < |ym-k - am+1| let am+1 = Xk+1 else let am+1 = ym-k+1
a1 a2 a3 a4 a5 a6 . . . am-2 am-1 am am+1
w1 w2 v1 w3 w4 y3 v2 w5 wi vm-i
|wi - am+1| << |Xk - am+1| < |ym-k - am+1|
Figure 2.1:
To obtain an optimal solution for the sequence s = 〈a1, a2, . . . , am, am+1〉
we look at the values of |xk − am+1| and |ym−k − am+1|; if |xk − am+1| <
|ym−k − am+1| then we add am+1 to s1 by setting xk+1 = am+1; otherwise we
add am+1 to s2 by setting ym−k+1 = am+1.
Unfortunately this does not necessarily produce an optimal solution for the
sequence s = 〈a1, a2, . . . , am, am+1〉 for the following reason. There might be
another, suboptimal way to split the sequence s = 〈a1, a2, . . . , am〉 into two
sequences 〈w1, w2, . . . , wi〉 and 〈v1, v2, . . . , vm−i〉, i.e., such that
i∑
u=1
|wu+1 − wu|+
m−i∑
u=1
|vu+1 − vu| >
k∑
u=1
|xu+1 − xu|+
m−i∑
u=1
|yu+1 − yu|
but such that |wi−am+1| is much smaller than |xk−am+1| and |ym−k−am+1|,
so that
i∑
u=1
|wu+1 − wu|+
m−i∑
u=1
|vu+1 − vu|+ |wi − am+1| < k∑ u=1 |xu+1 − xu|+ m−i∑ u=1 |yu+1 − yu|+ min(|xk − am+1|, |ym−k − am+1|); see the bottom of Figure 2.1. To solve this problem we generalize it to the following “two dimensional” prob- lems for all i < j ≤ n: Subproblem P(i,j): Split the subsequence s = 〈a1, a2, . . . , aj〉 into two sequences such that one ends with ai and the other with aj such that the sum of their total variations is minimal. 5 a1 a2 a3 a4 a5 a6 . . . ai ai+1 … aj-1 aj a1 a2 a3 a4 a5 a6 . . . am ai=aj-1 aj Figure 2.2: To obtain a solution for the subproblem P (i, j) from the previously obtained solutions we consider two cases. 1. If i < j−1 (see Figure 2.2 top) then we simply extend the optimal solution for P (i, j− 1) by adding aj to the subsequence ending with aj−1, because this is the only option, since the other sequence must have ended with ai. 2. If i = j−1 (see Figure 2.2 bottom) then we consider optimal solutions for all subproblems P (m, j − 1) for all m < j − 1 extending the subsequence ending with am and choosing m which results in the smallest total varia- tion of such obtained sequences. We now compare such minimal value with a solution in which one sequence is the entire sequence 〈a1, a2, . . . , aj−1〉 and the other sequence just the singleton 〈aj〉 and pick the one which has the smaller total variance as the solution for the problem P (i, j). Exercise: Reduce the above solution to a “single dimension”. (Hint: simply consider only problems of the form P (i− 1, i). 6