|An electronic component A has a size (sizeA), a number of inputs (inpA), and a
number of outputs (outpA). We can join component A to component B if
inpB = outpA.
The result is a new component C, where sizeC = sizeA + sizeB, inpC = inpA, and
outpC = outpB. The cost of joining A to B includes testing the resulting component,
so it depends on the sizes of A and B
and on the number of inputs and outputs. We estimate that the cost to join
A to B is
where connections equals outpA which equals inpB.
- cost = (inpA + sizeA) * connections * (outpB + sizeB)
We have a sequence of n components, each of size 1, that we must assemble into
bigger and bigger components until we have assembled them into a single component.
This will require us to perform n-1 joins.
The order of the components may not be changed, but the order in which we perform
the joins should be chosen to minimize the sum of the costs.
class Assemble that contains a method minCost that takes connect, the
sequence of the number of connections between adjacent components, as input and
returns the minimum cost of assembling them into one component.
The first element in connect is the number of inputs to the first component,
and the last element in connect is the number of outputs of the last component.
Otherwise, the i-th element is both the number of outputs of component i-1 and the number of
inputs of component i.