Google Code Jam 2009 1C: Bribe the Prisoners

Problem
The problem statement describes a prison with adjacent cells and a set of prisoners to be released. The problem is essentially to find the ordering of prisoners to be released such that the total number of occupied adjacent cells is minimal (and thus less coins need to be handed out).

Solution
Let be the set of cells in which a prisoner to be released resides. Assume is the optimal prisoner to be released first. The first thing we need to do is to give every prisoner left a gold coin as they all find out about leaving. We are now left with two sub-arrays and where we need to calculate the next best prisoner to be released in each array. For the sub-array we can iterate over the prisoners to be released residing in this range and find for each one the minimum number of coins if they were to leave and split the sub-array (making two more similar problems).

Note: The minimum number of coins for a sub-array [a,b] can be memoised as the solutions to the sub-problems overlap.

Here is the solution code provided by Google with a couple of additional comments:

int p[200]; // prisoners to be released.
map<pair<int, int>, int> dp;

// Finds the minimum amount of gold needed, 
// if we only consider the cells from a to b, inclusive.
int Solve(int a, int b) {
  // First, look up the cache to see if the 
  // result is computed before.
  pair<int, int> pr(a, b);
  if(mp.find(pr) != mp.end()) return mp[pr];

  // Start the computation.
  int r = 0;
  // For each prisoner to be released in the range a<=p_i<=b
  for(int i=0; i<Q; i++) {
    if(p[i] >= a && p[i] <= b) {
      // b-a prisoners find out about p[i] leaving and we are left with two
      // sub-arrays that need to be solved in a similar fashion.
      int tmp = (b-a) + Solve(a, p[i]-1) + Solve(p[i]+1, b);
      // Is the number of coins for the release of p[i] minimal?
      if (!r || tmp<r) r=tmp;
    }
  }
  mp[pr]=r;
  return r;
}