Received this on a mock interview, but we ran out of time to properly go over the optimal solution. All I know is it uses Dynamic Programming but I can't quite figure it out. Any ideas?

Given 2 cities and j days represented in a i x j 2D array that gives the profit attained by being in that city for the city, figure out the maximum profit possible after traveling j days. Note there is a assymmetric cost in moving between cities. Picking your starting city has no associated cost.

City1:      23  9   100 37
City2:      89  45  12  44

Cost 1 -> 2: 34
Cost 2 -> 1: 77