Finding a recursive formula for dynamic programming problem

Question

I have been presented with a problem I am supposed to use dynamic programming on, but I am really stuck. I really want to understand exactly how to approach this.

The problem is as follows: You are given an array of size N, each entry represents a city with a given value. At each round, you must choose where to build a wall. The "enemy" then chooses which side (either east or west) to attack from, destroying all of the cities up until the wall. You only collect value from the cities that still exist. The enemy destroys cities optimally meaning it always minimizes the amount of value you can get at the END of the game (not minimized per round, greedily).

A quick example:

Array: 8, 6, 2, 4, 2

1st Round - Best option is to build between city of value 6 and of value 2. The enemy attacks from the west which results in value of 8 to be collected.

2nd Round - Best option is to build between city of value 2 and of value 4. The enemy attacks from the east which results in value of 2 to be collected.

Total value for this game was 10.

I'm looking to find a recursive formula for the maximum possible value I can get in each game. I want to use this recursive formula to create a dynamic programming algorithm. Any help would be appreciated.

גלעד ברקן גלעד ברקן · Accepted Answer · 2019-12-04T14:15:08

Here's an idea that seems to work with the example you provided. Although without more tests to confirm, it may not be completely reliable, it can help you think about it. Please see the comments in the code. (The first two functions are to help calculate the subarray sums efficiently.)

function getPrefixSums(A){
  var ps = new Array(A.length + 1).fill(0)
  for (let i=0; i<A.length; i++)
    ps[i+1] = A[i] + ps[i]
  return ps
}

function getSum(ps, l, r){
  return ps[r+1] - ps[l]
}

function f(A, ps, l, r){
  // No moves available 
  if (l == r)
    return 0
  // One choice to place wall
  if (l + 1 == r)
    return Math.min(A[l], A[r])
    
  // For each of our available choices,
  // the enemey will choose the side
  // that guaratees we get the least.
  // Choose the BEST of these.
  let goodForUs = -Infinity

  for (let i=l+1; i<=r; i++){
    let west = getSum(ps, i, r) + f(A, ps, i, r)
    let east = getSum(ps, l, i-1) + f(A, ps, l, i-1)

    if (east > west){
      // Enemy chose west
      if (west > goodForUs)
        goodForUs = west
      
    // Enemy chose east
    } else if (east > goodForUs){
      goodForUs = east
    }
  }
  
  return goodForUs
}

var A = [8, 6, 2, 4, 2]
var ps = getPrefixSums(A)

console.log(f(A, ps, 0, A.length-1))

Finding a recursive formula for dynamic programming problem

1 Answers