title: Dynamic Programming Maximum Profit for Movers in 2 cities
body: <p>There is a moving company. It operates in two cities. They wish to maximize profit. Given are 2 arrays representing the two cities. The value at position i in each of the arrays indicates the maximum profit to be made in the city that day. If they work in city A on day i, and city B on day i+1, there is a cost associated with travelling between the 2 cities c. We need to use Dynamic Programming to find the maximum profit to be made. Here is an example:</p>
  
  <pre><code>A = {10, 20, 30}
  B = {-10, 50, 20}
  c = 20
  optimal solution = (10 + (50 - 20) + 20) = 10 + 30 + 20 = 60
  </code></pre>
  
  <p>I think this is similar to weighted interval schedule OR the subset sum problem (knapsack). Any help is appreciated.</p>
  
  <p>EDIT:</p>
  
  <p>I need to find the recurrence relation(s), time complexity of the algorithm and then prove the correctness. Any ideas?</p>