Algorithm for maximizing happiness when distributing objects to 2 groups

Question

You have an array of n fruits you must give to 2 people, X and Y. X will gain x_i happiness when eating the ith fruit, Y will gain y_i happiness when eating the ith fruit. We want to maximize total happiness of X and Y. The distribution of fruits does not have to be equal--you could give them all to X or all to Y.

You must give the fruit to X in Y in order (from the 1st to the nth fruit), and X and Y will ingest the fruit immediately upon receiving the fruit.

There is some difference in taste metric that affects how happy X and Y are to eat each fruit. This difference is defined by the function T(i,j), and is lookup-able in a table (costs O(1) to look up). So if X has just ingested fruit i, and is then given fruit j, X's happiness will increase by (x_j - T(i,j)).

I feel like this question should be solved via dynamic programming or maybe using a greedy algorithm but am having trouble formulating a solution. What I've done so far:

I know brute force is (2^n), since all combinations of fruit allocations to X and Y would be 2^n. I've tried doing a DP with [i,j,k] with i and j being the starting and ending fruits in n and k being the number of fruits you give to the first person (X). The solution with that DP would be max over k for any k of DP[0,n,k], but I can't seem to formulate beyond the base cases (am having trouble making the equation for DP[i,j,k])...

Answer 1

This can be solved in quadratic time in n using dynamic programming. Let f(i, j) be the maximum possible happiness if last fruit eaten by X is i and last fruit eaten by Y is j. Let me call the first fruit the fruit number 0 and the last one the number n - 1 (0-indexed). Then, you need to calculate f(-1, -1) (initially they have not eaten any fruit).

This dynamic programming can be easily calculated because if you know the last fruit eaten by both of them, you know the next fruit to be eaten.

The following C-like pseudocode has the details:

int dp(int i, int j) {
  //Get the current fruit
  int current = max(i, j) + 1;

  //Base case (I consider the first to be 0, so the last is n - 1)
  if (current == n) return 0;

  //Check if the value is calculated
  if (not calculated[i][j]) {
    calculated[i][j] = true;
    M[i][j] = max(dp(current, j) + x[current] - T(i, current), 
                  dp(i, current) + y[current] - T(j, current));
  }

  return M[i][j];
}