CS计算机代考程序代写 AI algorithm Algorithms Tutorial 4

(Note: arg min returns the value of j that produces the minimal value of
opt(j) + F (j, i)). The minimum cost is opt(n). To get the sequence, we
backtrack from post n giving the sequence {n, from(n), from(from(n)), …, 1}.
Reverse this to get the boat’s journey.

The complexity is O(n2) because there are n subproblems, and each subproblem
takes O(n) to find the best previous trading post.

2. You are given a set of n types of rectangular boxes, where the ith box has
height hi, width wi and depth di. You want to create a stack of boxes which is
as tall as possible, but you can only stack a box on top of another box if the

1

dimensions of the 2-D base of the lower box are each strictly larger than those
of the 2-D base of the higher box. Of course, you can rotate a box so that any
side functions as its base. It is also allowable to use multiple instances of the
same type of box.

Solution: First, since each box type has six different box rotations (there are
three faces and each face can be rotated once, exchanging width and depth),
it is easier to treat these rotations as being separate boxes entirely. This gives
6n boxes in total, and allows us to assume that boxes cannot be rotated. We
now order these boxes in a decreasing order of the surface area of their base.
Notice that in this way if a box B1 can go on top of a box B0 then B0 precedes
box B1 in such an ordering.

We aim to solve the following subproblem: What is the maximum height pos-
sible for a stack if the top most box is box number i? The recursion is:

opt(i) = max{opt(j) + hi : over all j such that wj > wi and dj > di}.

The final solution of the problem is the maximum value returned by any of
these subproblems, i.e., max1≤i≤6n opt(i).

The complexity is O(n2). There are 6n different subproblems, and each sub-
problem requires us to search through O(6n− 1) boxes to find ones that have
a base large enough to stack the current box on top.

3. You have an amount of money M and you are in a candy store. There are n
kinds of candies and for each candy you know how much pleasure you get by
eating it, which is a number between 1 and 100, as well as the price of each
candy. Your task is to chose which candies you are going to buy to maximise
the total pleasure you will get by gobbling them all.

Solution: This is a knapsack problem with duplicated values. The pleasure
score is the value of the item, the cost of a particular type of candy is its weight,
and the money M is the capacity of the knapsack. The complexity is O(Mn).

4. Consider a 2-D map with a horizontal river passing through its centre. There
are n cities on the southern bank with x-coordinates a1 . . . an and n cities on
the northern bank with x-coordinates b1 . . . bn. You want to connect as many
north-south pairs of cities as possible, with bridges such that no two bridges
cross. When connecting cities, you are only allowed to connect the the ith city
on the northern bank to the ith city on the southern bank.

Solution:

2

Sort the cities on the south bank according to their x coordinates and then
re-enumerate them so that they appear as {1, 2, 3, . . .}, and then apply the
same permutation to the cities on the north bank. Now the problem reduces
to finding a maximal increasing sequence of indices of cities on the north bank.

5. You are given a boolean expression consisting of a string of the symbols true and
false and with exactly one operation and, or, xor between any two consecutive
truth values. Count the number of ways to place brackets in the expression
such that it will evaluate to true. For example, there is only 1 way to place
parentheses in the expression true and false xor true such that it evaluates to
true.

Solution: Let there be n symbols, and n − 1 operations between them. We
solve the following two subproblems: How many ways are there to place brack-
ets to make the expression starting from at the lth symbol and ending at rth

symbol evaluate to true (T), and many ways are there to place brackets to
make the expression starting from at the lth symbol and ending at rth symbol
evaluate to false (F)? For example in “true and false xor true”, T(1, 2) would
be the number of ways of making “true and false” evaluate to true with correct
bracketing (in this case, T(1, 2) = 0).

The base case is that T(i, i) is 1 if symbol i is true, and 0 if symbol i is false.
The reverse applies to F(i, i).

Otherwise, for each subproblem, we ‘split’ the expression around an operator
m so that everything to the left of the operator is in its own bracket, and
everything to the right of the operator is in its own bracket to form two smaller
expressions. For example, splitting the sample expression around “xor” would
give “(true and false) xor (true)”. We then evaluate the subproblems on each
of the two sides, and combine the results together depending on the type of
operator we are splitting by, and whether we want the result to evaluate to
true or false. We solve both subproblems in parallel:

T(l, r) =
r−1∑
m=l

TSplit(l,m, r)

F(l, r) =
r−1∑
m=l

FSplit(l,m, r)

3

TSplit(l,m, r) =




T(l,m)× T(m + 1, r)
if operator m is ‘and’,

T(l,m)× F(m + 1, r) + T(l,m)× T(m + 1, r) + F(l,m)× T(m + 1, r)
if operator m is ‘or’,

T(l,m)× F(m + 1, r) + F(l,m)× T(m + 1, r)
if operator m is ‘xor’.

FSplit(l,m, r) =




T(l,m)× F(m + 1, r) + F(l,m)× F(m + 1, r) + F(l,m)× T(m + 1, r)
if operator m is ‘and’,

F(l,m)× F(m + 1, r)
if operator m is ‘or’,

T(l,m)× T(m + 1, r) + F(l,m)× F(m + 1, r)
if operator m is ‘xor’.

Note that the equations inside the TSplit and FSplit functions are chosen to
correspond with the truth tables of the corresponding operator.

The complexity is O(n3). There are O(n2) different ranges that l and r could
cover, and each needs the evaluations of TSplit or FSplit at up to n−1 different
splitting points.

6. A company is organising a party for its employees. The organisers of the party
want it to be a fun party, and so have assigned a fun rating to every employee.
The employees are organised into a strict hierarchy, i.e., a tree rooted at the
president. There is one restriction, though, on the guest list to the party:
an employee and their immediate supervisor (parent in the tree) cannot both
attend the party (because that would be no fun at all). Give an algorithm that
makes a guest list for the party that maximises the sum of the fun ratings of
the guests.

Solution: Let us denote by T (i) the subtree of the tree T of all employees
which is rooted at an employee i. For each such subtree we will compute two
quantities, I(i) and E(i). I(i) is the maximal sum of fun factors fun(i) of
employees selected from subtree T (i) which satisfies the constraint and which
must include the root i. E(i) is the maximal sum of fun factors of employees
selected from the subtree T (i) but which does NOT include i. These two quan-
tities are easily computed by recursion on subtrees, starting from the leaves.

4

For every employee i whose (immediate) subordinates are j1, . . . , jm we have

I(i) = fun(i) +
∑

1≤k≤m

E(jk)

E(i) =
∑

1≤k≤m

max(E(jk), I(jk))

Notice that in the definition of E(i) we have the option to either include the
children of i or exclude them, whatever produces larger value of E(i). The final
answer is max(I(n), E(n)) where n is the root of the corporate tree T . Clearly
such algorithm runs in time linear in the number of all employees.

7. You have n1 items of size s1 and n2 items of size s2. You would like to pack all
of these items into bins, each of capacity C, using as few bins as possible.

Solution: We will solve subproblems P (i, j) of packing i many items of size
s1 and j many items of size s2 for all 1 ≤ i ≤ n1 and all 1 ≤ j ≤ n2. Let
C/s1 = K. The recursion step is essentially an exhaustive search:

opt(i, j) = 1 + min
0≤k≤K

opt(i− k, j − b(C − k s1)/s2c)

Thus, we try all options of placing between 0 and K many items of size s1
into one single box and then fill the box to capacity with items of size s2, and
optimally packing the remaining items. The algorithm runs in time O(K n1 n2).

8. You are given n activities and for each activity i you are given its starting time
si, its finishing time fi and the profit pi which you get if you schedule this
activity. Only one activity can take place at any time. Your task is to design
an algorithm which produces a subset S of those n activities so that no two
activities in S overlap and such that the sum of profits of all activities in S is
maximised.

Solution: Sort all activities by finishing time fi. We solve the following sub-
problems for all i: What is the maximum profit opt(i) we can make if we are
to choose between activities a1, a2, . . . , ai and such that activity i is the last
activity we do? Recursion is simple:

opt(i) = max{opt(j) : fj < si}+ pi prev(i) = arg max{opt(j) : fj < si} Finally, the solution to the original problem is profit of max1≤i≤n opt(i) and the sequence of jobs can be obtained starting with m = arg max1≤i≤n opt(i) and then backtracking via m, prev(m), prev(prev(m)), . . .. 5 9. Your shipping company has just received N individual shipping requests (jobs). For each request i, you know it will require ti trucks to complete, paying you di dollars. You have T trucks in total. Devise an algorithm to select jobs which will bring you the largest possible amount of money. Solution: This is just the standard knapsack problem with ti being the size of the ith item, di its value and with T as the capacity of the knapsack. Since each transportation job can be executed only once, it is a knapsack problem with no duplicated items allowed. The complexity is O(NT ). 10. Again your shipping company has just received N individual shipping requests (jobs). This time, for each request i, you know it will require ei employees and ti trucks to complete, paying you di dollars. You have E employees and T trucks in total. Devise an efficient algorithm to select jobs which will bring you the largest possible amount of money. Solution: This is a slight modification of the knapsack problem with two constraints on the total size of all jobs; think of a knapsack which can hold items of total weight not exceeding E units of weight and total volume not exceeding T units of volume, with item i having a weight of ei integer units of weight and ti integer units of volume. For each triplet(e, t, i) such that e ≤ E, t ≤ T, i ≤ N we solve the following subproblem: choose a sub-collection of items 1 . . . i that fits in a knapsack of capacity e units of weight and t units of volume, which is of largest possible value, putting such a value in a 3D table of size E × T × N where N is the number of items (in this case jobs). These values are obtained using the following recursion: opt(i, e, t) = max{opt(i− 1, e, t), opt(i− 1, e− ei, t− ti) + di}. The complexity is O(NET ) 11. Because of the recent droughts, n proposals have been made to dam the Murray Darling river. The ith proposal asks to place a dam xi meters from the head of the river (i.e., from the source of the river) and requires that there is not another dam within ri metres (upstream or downstream). What is the largest number of dams that can be built? You may assume that xi < xi+1. Solution: We solve this by finding the maximum value among the following subproblems for every i ≤ n: Find the largest possible number of dams that can be built among proposals 1 . . . i, such that the ith dam is built. The base case is opt(1) = 1. The recursion is: opt(i) = 1 + max{opt(j) : xi − xj > max(ri, rj), j < i} 6 We do an O(n) search at every dam proposal i. Thus, the total complexity is O(n2). 12. You are given an n × n chessboard with an integer in each of its n2 squares. You start from the top left corner of the board; at each move you can go either to the square immediately below or to the square immediately to the right of the square you are at the moment; you can never move diagonally. The goal is to reach the right bottom corner so that the sum of integers at all squares visited is minimal. a) Describe a greedy algorithm which attempts to find such a minimal sum path and show by an example that such a greedy algorithm might fail to find such a minimal sum path. b) Describe an algorithm which always correctly finds a minimal sum path and runs in time n2. c) Describe an algorithm which computes the number of such minimal paths. d) (Very Tricky!) Assume now that such a chessboard is stored in a read only memory. Describe an algorithm which always correctly finds a minimal sum path and runs in linear space (i.e., amount of read/write memory used is O(n)) and in time O(n2). m n 7 Solution: a) Start at the top left square, and always go to the immediate square below or to the right that has the smallest integer. This algorithm fails with the following example: 0 1 1 5 1000 1000 5 5 0 The algorithm will get a score of 1002, instead of the correct answer of 15. b) We solve all subproblems of the form “What is the best score we can get arriving at the cell at row i and column j”? The base case is that opt(1, 1) = board(1, 1), and opt(i, j) = ∞ for all i and j that are off the board. The recursion is: opt(i, j) = board(i, j) + min{opt(i− 1, j), opt(i, j − 1)}. The complexity is O(n2). c) Solve the following subproblem: What is the minimum number of ways to reach row i and column j with the score opt(i, j)? The base case is ways(1, 1) = 1 and ways(i, j) = 0 for all i and j that are off the board. The recursion is: ways(i, j) =   ways(i− 1, j) if opt(i− 1, j) < opt(i, j − 1) ways(i, j − 1) if opt(i− 1, j) > opt(i, j − 1)
ways(i− 1, j) + ways(i, j − 1) if opt(i− 1, j) = opt(i, j − 1)

The complexity is once again O(n2)

d) This is a very tricky one. The idea is to combine divide and conquer
with dynamic programming. Note that to generate optimal scores at a row i
you only need the optimal scores of the previous row. You start running the
previous algorithm from the top left cell to the middle row bn/2c, keeping in
memory only the previous row. You now run the algorithm from the bottom
right corner until you reach the middle row, always going either up one cell
or to the left one cell. Once you reach the middle row you sum up the scores
obtained by moving down and to the right from the top left cell and the scores
obtained by moving up and to the left from the bottom right cell and you

8

pick the cell C(n/2,m) in that row with the minimal sum. This clearly is
the cell on the optimal trajectory. You now store the coordinates of that
cell and proceed with the same strategy applied to the top left region for
which C(n/2,m) is bottom right cell, and also applied to the bottom right
region of the board for which C(n/2,m) is the top left cell. The run time is
O(n× n + n× n/2 + n× n/4 + . . .) = O(n× 2n) = O(n2)

13. A palindrome is a sequence of letters which reads equally from left to right
and from right to left. Given a sequence of letters, find efficiently its longest
subsequence (not necessarily contiguous) which is a palindrome. Thus, we are
looking for a longest palindrome which can be obtained by crossing out some
of the letters of the initial sequence without permuting the remaining letters.

Solution: Let Si denote the i
th letter of the string. Solve the subproblem:

What is the longest palindrome within the substring starting at letter i and
ending at j. The base case is that opt(i, i) = 1, as a single letter is a palindrome
by itself. We solve this using the recursion:

opt(i, j) =




1 if i = j,

2 if i + 1 = j and Si = Sj,

opt(i + 1, j − 1) + 2 if Si = Sj and i < j − 2, max{opt(i, j − 1), opt(i + 1, j)} else and a function from pairs of natural numbers into pairs of natural numbers pred[(i, j)] =   (i, i) if i = j, (i, j) if i + 1 = j and Si = Sj, (i + 1, j − 1) if Si = Sj and i < j − 2, (i, j − 1) if Si 6= Sj and opt(i, j − 1) ≥ opt(i + 1, j) (i + 1, j) else To reconstruct the palindrome, backtrack iterating function pred[(i, j)] starting with (1, n) and recoding values of i and j when Si = Sj. The complexity of this algorithm is O(n2), where n is the length of the string. 14. A partition of a number n is a sequence 〈p1, p2, . . . , pt〉 (we call the pk parts) such that 1 ≤ p1 ≤ p2 ≤ . . . ≤ pt ≤ n and such that p1 + . . . + pt = n. (a) Find the number of partitions of n in which every part is smaller or equal than k, where n, k are two given numbers such that 1 ≤ k ≤ n. 9 (b) Find the total number of partitions of n. Solution: (a) Let numpart(k,m) denote the number of partitions of m in which every part is at most k. Then for all m numpart(1,m) = 1 because the only way to represent m with k = 1 would be as a sum of m ones; for k ≥ 2 the value of numpart(k,m) satisfies the recursion numpart(k,m) = numpart(k − 1,m) + numpart(k,m− k) The first term on the right counts number of partitions of m when no part is equal k and the second term counts the number of partitions when there exists at least one part equal to k, which we subtract from m and look at the number of partitions of the remainder m− k in which all the parts are also at most k. Note that numpart(k,m) are computed in order of the value of the sum m+k. (b) We run the previous algorithm; the solution is numpart(n, n). 15. We say that a sequence of Roman letters A occurs as a subsequence of a sequence of Roman letters B if we can obtain A by deleting some of the symbols of B. Design an algorithm which for every two sequences A and B gives the number of different occurrences of A in B, i.e., the number of ways one can delete some of the symbols of B to get A. For example, the sequence ba has three occurrences in the sequence baba: baba, baba, baba. Solution: Let Ai be the i th letter of A, and Bj be the j th letter of B. Solve the subproblems: How many times do the first i letters of A appear as a subsequence of the first j letters of B. The base case is ways(1, 1) = 1 if A1 = B1 and 0 otherwise; also, clearly, ways(i, j) = 0 if i > j. The recursion
is, for all i < j opt(i, j) =   0, if i > j

opt(i, j − 1), if Ai 6= Bj
opt(i− 1, j − 1) + opt(i, j − 1) if Ai = Bj

Note that in the second case when Ai = Bj we have two options: we can map
Ai into Bj because they match, but we can also map the first i many letters of
A into j − 1 many letters of B, so we have the sum of these two options. The
complexity is O(nm) where n is the length of A and m is the length of B.

16. We are given a checkerboard which has 4 rows and n columns, and has an
integer written in each square. We are also given a set of 2n pebbles, and we

10

want to place some or all of these on the checkerboard (each pebble can be
placed on exactly one square) so as to maximise the sum of the integers in the
squares that are covered by pebbles. There is one constraint: for a placement
of pebbles to be legal, no two of them can be on horizontally or vertically
adjacent squares (diagonal adjacency is fine).

(a) Determine the number of legal patterns that can occur in any column (in
isolation, ignoring the pebbles in adjacent columns) and describe these
patterns.

Call two patterns compatible if they can be placed on adjacent columns
to form a legal placement. Let us consider sub-problems consisting of the
first k columns 1 ≤ k ≤ n. Each sub-problem can be assigned a type,
which is the pattern occurring in the last column.

(b) Using the notions of compatibility and type, give an O(n)-time algorithm
for computing an optimal placement.

Solution: (a) There are 8 patterns, listed below.

1 2
O

3

O

4

O

5

O

6
O

O

7

O

O

8
O

O

(b) Let t denote the type of pattern, so that t ranges from 1 to 8. We solve
our subproblem by choosing k columns from our set of patterns, such that each
column is compatible with the one before. The subproblem is: What is the
maximum score we can get by only placing pebbles in the first k columns, such
the kth column has pattern t. The base case is that opt(0) = 0. The recursion
is:

opt(k, t) = score(k, t) + max{opt(k − 1, s) : s is compatible with t}

Here, score(k, t) is the score obtained by using pattern t on column k. The
compatibilities are as follows:

(a) pattern 1 is compatible with all 8 patterns (including itself);

11

(b) pattern 2 is compatible with all patterns except 2,6 and 8

(c) pattern 3 is compatible with all patterns except 3 and 7;

(d) pattern 4 is compatible with all patterns except 4 and 6;

(e) pattern 5 is compatible with all patterns except 5,7 and 8;

(f) pattern 6 is compatible with all patterns except 2,6 and 8;

(g) pattern 7 is compatible with all patterns except 3,5,7 and 8;

(h) pattern 8 is compatible with all patterns except 2,5,6,7 and 8.

The complexity is O(n), as the number of patterns is constant.

17. Skiers go fastest with skis whose length is about their height. Your team
consists of n members, with heights h1, h2, . . . , hn. Your team gets a delivery
of m ≥ n pairs of skis, with lengths l1, l2, . . . , lm. Your goal is to design an
algorithm to assign to each skier one pair of skis to minimise the sum of the
absolute differences between the height hi of the skier and the length of the
corresponding ski he got, i.e., to minimise∑

1≤i≤n

|hi − ls(i)|

where s(i) is the index of the skies assigned to the skier of height hi.

Solution: First observe that if we have two skiers i and j such that hi < hj, then s(i) < s(j). If this were not the case, we could swap the skis assigned to i and j, which would lower the sum of differences. This implies that we may initially sort the skiers by height, and sort the skis by length, and find some sort of pairing such that there are no crossovers (similar to question 4). Also, if you have equal number of skiers and skis, you would give ith skier ith pair of skis. We now solve the following subproblem: What is the minimum cost of matching the first i skiers with the first j > i skis such that each of the first i skiers gets
a ski? The base case is opt(i, i) =

∑i
k=1 |hk − lk|. The recursion for j > i is:

opt(i, j) = min{opt(i, j − 1), opt(i− 1, j − 1) + |hi − lj|}.

To retrieve the assignment, we start at (i, j) where i = n and j = m. If
opt(i − 1, j − 1) + |hi − lj| < opt(i, j − 1) then s(i) = j and we try again at 12 (i − 1, j − 1). Otherwise, we try again at (i, j − 1). If at any point we reach i = j (our base case), we simply assign s(k) = k for all 1 ≤ k ≤ i. The complexity of the initial recursion O(nm). The complexity of retrieving the assignment is O(m), as each time we run the algorithm, j decreases by exactly 1. 18. You have to cut a wood stick into several pieces. The most affordable company, Analog Cutting Machinery (ACM), charges money according to the length of the stick being cut. Their cutting saw allows them to make only one cut at a time. It is easy to see that different cutting orders can lead to different prices. For example, consider a stick of length 10 m that has to be cut at 2, 4, and 7 m from one end. There are several choices. One can cut first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the resulting stick of 8 m, and the last one of 6 m. Another choice could cut at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is better for us. Your boss demands that you design an algorithm to find the minimum possible cutting cost for any given stick. Solution: Let x(i) be the distance along the stick the ith cutting point is at. Solve the following subproblem: What is the minimum cost of cutting up he stick completely from cutting point i to cutting point j. The base case is opt(i, i + 1) = 0. The recursion is: opt(i, j) = x(j)− x(i) + min{opt(i, k) + opt(k, j) : i < k < j}. The complexity is O(n2), where n is the number of cutting points on the stick. Note: always cutting the stick as close to its middle as possible does not always produce an optimal solution; try making a counter example. 19. For bit strings X = x1 . . . xm, Y = y1 . . . yn and Z = z1 . . . zm+n we say that Z is an interleaving of X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of the bits in X and Y. For example if X = 101 and Y = 01 then x1x2y1x3y2 = 10011 is an interleaving of X and Y, whereas 11010 is not. Give an efficient algorithm to determine if Z is an interleaving of X and Y. Solution: Solve the following subproblem: Do the first i bits of X and the first j bits of Y form an interleaving in the first i + j bits of Z? The base case is opt(0, 0) = true, and opt(i, j) = false if i < 0 or j < 0. The recursion is: opt(i, j) = (opt(i− 1, j) AND zi+j = xi) OR (opt(i, j − 1) AND zi+j = yj). 13 The complexity is O(nm). 20. Some people think that the bigger an elephant is, the smarter it is. To disprove this you want to analyse a collection of elephants and place as large a subset of elephants as possible into a sequence whose weights are increasing but their IQs are decreasing. Design an algorithm which given the weights and IQs of n elephants, will find a longest sequence of elephants such that their weights are increasing but IQs are decreasing. Solution: Sort the elephants in order of decreasing IQs. The problem now becomes finding the longest increasing subsequence of elephant weights. 21. You have been handed responsibility for a business in Texas for the next N days. Initially, you have K illegal workers. At the beginning of each day, you may hire an illegal worker, keep the number of illegal workers the same or fire an illegal worker. At the end of each day, there will be an inspection. The inspector on the ith day will check that you have between li and ri illegal workers (inclusive). If you do not, you will fail the inspection. Design an algorithm that determines the fewest number of inspections you will fail if you hire and fire illegal employees optimally. Solution: Observe that the minimum and the maximum number of illegal workers you could possible have on the evening of day i are max(K − i, 0) and K + i. We solve the following subproblem: What is the minimum number of inspections I have failed on day i assuming that on that day I have j many illegal workers? The base case is opt(0, K) = 0, since we start with 0 failed inspections before the first day begins. Let failed(i, j) return 1 if the j falls out of the range of [li, ri], and return 0 otherwise. The recursion is: for all i such that 1 ≤ i ≤ N and all j such that max(0, K − i) ≤ j ≤ K + i, opt(i, j) = failed(i, j)+min   { opt(i− 1, j − 1) if j − 1 ≥ max(0, K − (i− 1)), ∞ if j − 1 < max(0, K − (i− 1)) opt(i− 1, j),{ opt(i− 1, j + 1) if j + 1 ≤ K + i− 1 ∞ if j + 1 > K + i− 1

Note that the first option in the cases corresponds to hiring an illegal worker
on the morning of day i, providing that the number of workers on the previous
day was achievable over the period of i− 1 days (you start with K workers, so

14

after i − 1 days you must have at least K − (i − 1) workers which happens if
you kept firing one worker every day); the second corresponds to keeping the
same number of illegal workers as on the previous day and the third option
corresponds to firing a worker from the previous day. The final answer is equal
to min

max(K−N,0)≤j≤K+N
opt(N, j).

The complexity is O(N2), as there are N days, and at most 2N + 1 possible
values of illegal worker each day.

22. Given an array of N positive integers, find the number of ways of splitting the
array up into contiguous blocks of sum at most K.

Solution: Solve the subproblem: What is the number of ways I can split the
first i elements into contiguous blocks of sum at most K. The base case is
opt(0) = 1. For 1 ≤ j < i let sum(j, i) is the sum of all numbers from A[j] to A[i] inclusive. The recursion is: opt(i) = ∑ {opt(j − 1) : 1 ≤ j ≤ i, sum(j, i) ≤ K}, The complexity is O(n2), as each subproblem requires a O(n) search. 23. There are N levels to complete in a video game. Completing a level takes you to the next level, however each level has a secret exit that lets you skip to another level later in the game. Determine if there is a path through the game that plays exactly K levels. Solution: The subproblems are: Can I reach the ith level after playing exactly k levels? The base case is opt(0, 0) = true. The recursion is: opt(i, k) = opt(i− 1, k − 1) OR (∃j < i− 1)(opt(j, k − 1) AND link(j, i)) Here link(j, i) is true if and only if level j has a secret exit to level i. The final answer is opt(K,N). The time complexity is O(N2). 24. Given a sequence of n positive or negative integers A1, A2, ...An, determine a contiguous subsequence Ai to Aj for which the sum of elements in the subse- quence is maximised. Solution:We solve the subproblem: What is the maximum sum of elements ending with integer i? The base case is opt(0) = 0. The recursion is: opt(i) = Ai + max(0, opt(i− 1). 15 Here, we take the maximum of 0 and opt(i− 1) because we may either choose to add Ai to the previous block, or start a completely new block. To determine the actual block, we may also solve the following recursive function for all i: start(i) = { start(i− 1) if opt(i− 1) > 0,
i if opt(i− 1) ≤ 0

To get the block, we simply find the element i such that opt(i) is maximised.
The block with maximum sum is [start(i), i]. The complexity is O(n).

25. Consider a row of n coins of values v1, v2, …vn, where n is even. We play a
game against an opponent by alternating turns. In each turn, a player selects
either the first or last coin from the row, removes it from the row permanently,
and receives the value of the coin. Determine the maximum possible amount
of money we can definitely win if we move first.

Solution: DP has a very important role in the field of game theory. Let
opt(i, j) for i, j two integers such that j−i+1 an even number and 1 ≤ i < j ≤ n denote the maximal amount of money we can definitely win if we play on the subsequence between coins at the position i and position j. Then opt(i, j) satisfies the following recursion opt(i, j) = max{vi+min{opt(i+2, j), opt(i+1, j−1)}, vj+min{opt(i+1, j−1), opt(i, j−2)}} The options inside the min functions represent the choice your opponent takes, either to continue taking from the same end as you took or from the oposite end of the sequence. The problems to find opt(i, j) are solved in order of the size of j − i. The complexity is O(n2), because this is how many pairs of i, j we have and each stage of the recursion has only constant number of steps (4 table lookups and 2 additions plus two min and one max operations. 16