Necessary and Sufficient

Problem: Say you and your mate Gordon are playing a game called 2-Man Money Grab. In front of you are n bags of money lined up in an orderly fashion. You both know exactly how much is in each bag. The game goes as follows: each player in turn can pick a single bag from either end. Players alternate picking a bag and the person with the most money when all bags are chosen (there are an even number of bags) wins. You get to go first. What is your strategy?

Solution: This problem can be solved using dynamic programming because it exhibits the classic traits of optimal substructure and overlapping sub-problems. To see this let's first define some terminology.

Let m_i = the amount of money in the bag in position i
Let M[i,j] = the maximum amount of money you can win from the bags in position i through j inclusive.

Now faced with a choice from the range [i,j], per the rules of the game, you can only select the bag of money in position i or position j. Once you do this, and assuming Gordon isn't a dumb ass, he's going to make an optimal selection based on the remaining items, either [i+1,j] or [i,j-1]. Thus the amount of money you'd collect would be equal to the sum of the money available in this range less the money that Gordon made off with. We can express this algebraically as follows:

when j>i, otherwise when i=j it follows that M[i,j] = M[i,i] = m_i

This is a recurrence relationship. The solution for M[i,j] is expressed in terms of sub-problems. Thus, to solve the problem we need to pre-calculate all the "sigma" terms (the summations) then use these in the above formula using memoization to ensure that we don't repeat processing. This implies a run time complexity of O(N²) from the time required to compute the summations.

Here's some C# code to solve it:

private static int[,] _sum;

private static int[] _moneyBags;

private static int[,] _seen;

public static void Main(string[] args)

{

    _moneyBags = new[] {20, 11, 42, 13, 34, 5, 16, 27, 28, 25 };

    _sum = new int[_moneyBags.Length, _moneyBags.Length];

    _seen = new int[_moneyBags.Length, _moneyBags.Length];

    // initialise history table

    for (int i = 0; i < _moneyBags.Length; i++)

        for (int j = 0; j < _moneyBags.Length; j++)

            _seen[i, j] = -1;

    // find all summations

    for (int i = 0; i < _moneyBags.Length; i++)

    {

        int sum = 0;

        for (int j = i; j < _moneyBags.Length; j++)

        {

            sum += _moneyBags[j];

            _sum[i, j] = sum;

        }

    }

    var answer = BestSelection(0, _moneyBags.Length-1);

    Console.WriteLine( answer );

}

public static int BestSelection(int from, int to)

{

    if (_seen[from, to] != -1)

        return _seen[from, to];

    if (from == to)

        return _sum[from, to];

    var takeFirst = _sum[from,to] - BestSelection(from+1,to);

    var takeLast = _sum[from,to] - BestSelection(from,to-1);

    _seen[from, to] = takeFirst > takeLast ? takeFirst : takeLast;

    return _seen[from, to];

}