Every year, as part of its annual meeting, the Antarctican Snail Lovers of Upper Glacierville hold a
Round Table Mating Race. Several high-quality breeding snails are placed at the edge of a round
table. The snails are numbered in order around the table from 1 to n. During the race, each snail
wanders around the table, leaving a trail of slime behind it. The snails have been specially trained
never to fall off the edge of the table or to cross a slime trail, even their own. If two snails meet,
they are declared a breeding pair, removed from the table, and whisked away to a romantic hole
in the ground to make little baby snails. Note that some snails may never find a mate, even if the
race goes on forever.
For every pair of snails, the Antarctican SLUG race organizers have posted a monetary reward,
to be paid to the owners if that pair of snails meets during the Mating Race. Specifically, there
is a two-dimensional array M[1… n,1… n] posted on the wall behind the Round Table, where
M[i, j] = M[ j, i] is the reward to be paid if snails i and j meet.
Describe and analyze an algorithm to compute the maximum total reward that the organizers
could be forced to pay, given the array M as input.
Source:http://jeffe.cs.illinois.edu/teaching/algorithms/2009/notes/03-dynprog.pdf
Question 21 in document