Code: Select all
Suppose there are 4 boxes and 4 destinations. And lets consider that f(0001) means that the cost where the 4th destination is used and there is only one box. f(0010) returns the cost where the 3rd destination is used with box 1.
So, f(1001) returns the min cost such that the first two boxes are used and the 1st and the 4th destinations are used.
So, f(1101) returns the min cost such that the first three boxes are used and the 1st, 2nd and the 4th destinations are used. So, the number of '1's means the number of boxes. Right?
So, f(1111) is our desired result. And suppose cost[i][j] means the cost to connect the ith box to the jth destination.
Now we can build a recurrence
f(1111) = min ( f(1110) + cost[4][4], f(1101) + cost[4][3], f(1011) + cost[4][2],
f(0111) + cost[4][1] );