Ex. 11.28 Dynamic programming The Restaurant Mo e Restaurant Monopoly problem is the following. You are given a linear row of restauran he objective is to specify mergin of sizes Sil.n th bjective is to specify merging operations so that all of the restaurants are merged into a th At any step, only a pair of consecutive restaurants can be merged into a new restaurant that is the union of the two buildings. restaurant. The merging rules are as follows The size of the new restaurant is the sum of the sizes of the two restaurants being merged. The cost of a merge is equal to the size of the larger restaurant. The total cost of a sequence of n -1 mergings is the sum of the costs of the individual mergi The problem is to devise a two or three line high-level recursive dynamic programming specifica ngs computes the minimum total cost for creating one restaurant from the original n restaurants. The total the sum of all merging costs total cost is or creating one restaurant from the orignal n restaurants. The to Summary of the definitions Let Size(A) be the size of superrestaurantA For a simple restaurant i. Size(i) = S[i] and the size of a merged super restaurant is the sum of the individual original restaurants that have been merged together to form that monster super restaurant. The cost of merging the two consecutive monster super-restaurants A and B together to form superduper monste C is Merging Cost(A to be merged with B) max(Size(A), Size(B)), so if A has size Sti+Si+1]+.+SIH and B has the size Slk + 1] + Sk + 2] + . . . + S[j], then the cost to merge A and B together is MerginCost(already created A with already created B)