Dynamic Programming Practice Problems This site
contains a collection of practice dynamic programming problems and
their solutions. The problems listed below are also available in a pdf handout. To view the solution
to one of the problems below, click on its title. To view the
solutions, you'll need a machine which can view Macromedia Flash
animations and which has audio output. If you want, you can also view
a quick review from recitation on how to solve the integer knapsack problem (with
multiple copies of items allowed) using dynamic programming.
- Maximum Value Contiguous Subsequence. Given a
sequence of n real numbers A(1) ... A(n), determine a contiguous
subsequence A(i) ... A(j) for which the sum of elements in the
subsequence is maximized.
- Making Change. You are given n types of coin
denominations of values v(1) < v(2) < ... < v(n) (all integers).
Assume v(1) = 1, so you can always make change for any amount of money
C. Give an algorithm which makes change for an amount of money C with
as few coins as possible. [on problem set 4]
- Longest Increasing Subsequence. Given a sequence of n
real numbers A(1) ... A(n), determine a subsequence (not necessarily
contiguous) of maximum length in which the values in the subsequence
form a strictly increasing sequence. [on problem set 4]
- Box Stacking. You are given a set of n types of
rectangular 3-D boxes, where the i^th box has height h(i), width
w(i) and depth d(i) (all real numbers). 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 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.
- Building Bridges. Consider a 2-D map with a
horizontal river passing through its center. There are n cities on
the southern bank with x-coordinates a(1) ... a(n) and n cities
on the northern bank with x-coordinates b(1) ... b(n). 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
can only connect city i on the northern bank to city i on the southern
bank. (Note: this problem was incorrectly stated on the paper copies
of the handout given in recitation.)
- Integer Knapsack Problem (Duplicate Items
Forbidden). This is the same problem as the example above, except here it
is forbidden to use more than one instance of each type of item.
- Balanced Partition. You have a set of n integers
each in the range 0 ... K. Partition these integers into two
subsets such that you minimize |S1 - S2|, where S1 and S2
denote the sums of the elements in each of the two subsets.
- Edit Distance. Given two text strings A of length
n and B of length m, you want to transform A into B with a
minimum number of operations of the following types: delete a
character from A, insert a character into A, or change some
character in A into a new character. The minimal number of such operations
required to transform A into B is called the edit distance between
A and B.
- Counting Boolean Parenthesizations. You are given a
boolean expression consisting of a string of the symbols 'true',
'false', 'and', 'or', and 'xor'. Count the number of ways to
parenthesize the expression such that it will evaluate to true. For
example, there is only 1 way to parenthesize 'true and false xor true'
such that it evaluates to true.
- Optimal Strategy for a Game. Consider a row of
n coins of values v(1) ... v(n), 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
- Two-Person Traversal of a Sequence of Cities. You
are given an ordered sequence of n cities, and the distances between
every pair of cities. You must partition the cities into two
subsequences (not necessarily contiguous) such that person A visits
all cities in the first subsequence (in order), person B visits all cities
in the second subsequence (in order), and such that the sum of the total
distances travelled by A and B is minimized. Assume that person A and
person B start initially at the first city in their respective
- Bin Packing (Simplified Version). You have n1
items of size s1, n2 items of size s2, and n3 items of
size s3. You'd like to pack all of these items into bins each of
capacity C, such that the total number of bins used is minimized.