In this task we will see an example of parameter reduction in DP.

Broadly speaking, parameter reduction consists of eliminating some parameter in a DP formulation that can be deduced from the others.

To illustrate this, consider the following simple problem. You have \(n\) candies to give to 3 kids. Each candy has a value \(w_i\) that represents how good it is. All kids agree on these values. The goal is to split the candies amongst the kids so that the difference between the maximum total value and the minimum total value given to a kid is minimum.

More formally, is \(V_i\) is the sum of the values of the candies given to the \(i\)-th kid then the goal is to minimize the balance of the candy distribution, that is, minimize \(max(V_1, V_2, V_3) - min(V_1, V_2, V_3)\).

Example

Consider the 6 candies \(c_1, c_2, c_3, c_4, c_5, c_6\) shown in the picture below:

If we give \(c_1, c_2\) to the first kid, \(c_3, c_4\) to the second kid and \(c_5, c_6\) to the third kid, we have \(v_1 = 4 + 3 = 7\), \(v_2 = 4 + 3 = 5\) and \(v_3 = 4 + 3 = 6\). So, in this case, the balance of the candy distribution is \(max(7, 5, 6) - min(7, 5, 6) = 7 - 5 = 2\).

But we can do better! We can instead give \(c_1, c_3\) to the first kid, \(c_2, c_4\) to the second kid and \(c_5, c_6\) to the third kid. In this case \(v_1 = v_2 = v_3 = 6\) so the balance is 0.

This problem is very naturally formulated as a top-down DP. For each candy we have 3 possible options: give to either the first, the second or the third kid. As with the Knapsack problem, the order in which we make the decisions does not matter and thus as far as the candies are concerned, we only need to keep track of the index \(i\) of the next candy for which we are going to make a decision. On the other hand, only after making all the decisions we can evaluate the balance of the candy distribution. Therefore, we also need to keep track of the total value given to each of the kids.

Thus a possible state can be a tuple \((i, v_1, v_2, v_3)\) meaning that we have already given candies \(0, \ldots, i - 1\) making a total values of the \(i\)-th kid equal to \(v_i\).

We can thus define the subproblems as:

\(dp(i, v_1, v_2, v_3)\) is the minimum difference that we can achieve by giving candies \(i, i + 1, \ldots, n - 1\) knowing that the \(k\)-th kid has already value \(v_k\).

The original problem is clearly \(dp(0, 0, 0, 0)\). The recurrence relation easily follows from the three possible actions that we can perform for each candy:

When \(i = n\) we have finished distributing the candies. We can then define:

The number of states in this solution is \(O(n S^3)\) where \(S\) is the sum of all the values of the candies. Since each state takes constant time to evaluated, that will be the runtime of this solution.

By now it should be easy to write the code corresponding to this solution. If you tried to do it and you still have trouble, you can find it here.

Our goal in this task is to reduce the state space from tuples \((i, v_1, v_2, v_3)\) to tuples \((i, v_1, v_2)\). This will be possible because we can deduce \(v_3\) from \(v_1, v_2\). We only need the value of \(v_3\) in the end, when all candies have been distributed. At that moment, we know that \(v_1 + v_2 + v_3 = S\), the total value of the candies. Therefore, \(v_3 = S - v_1 - v_2\).

We can redefine our subproblems as follows:

\(dp(i, v_1, v_2)\) is the minimum difference that we can achieve by giving candies \(i, i + 1, \ldots, n - 1\) knowing that the first kid has value \(v_1\) and the second has \(v_2\).

The recurrence is almost the same as before, except that we drop the last parameter:

When \(i = n\) we use the fact that \(v_3 = S - v_1 - v_2\) to evaluate the balance: