Solve this problem with dynamic programming. Identify the base case, dynamic array, and solution, then write a program in python to solve the following problem. Your friend likes to mess with you by giving you every-day tasks made tricky. This time, the task is the following. You have a round cake and you want to cut it into as many pieces as possible but only certain cuts are allowed. Each allowed cut must go completely from one side of the cake to the other. Once a cut is made, the cuts that crossed this cut are no longer feasible. Ok, this puzzle is a bit annoying so let's simplify it. Starting at any point on the circumference of the cake, label the starting points of each cut with the integers 1, 2...., n where 1 is one end of an arbitrary cut, 2 is the next distinct end of a cut that is clockwise from 1, and n is the last distinct end of a cut (in the clockwise direction, which is the same as the first distinct end of a cut in the counter-clockwise direction). With these points labeled as such we can then describe the possible cuts by an x n matrix M where mij = 1 if the cut from i toj is allowed and 0 otherwise. For example consider cutting the cake between four points where cuts are allowed between 1 and 3, 1 and 4, and 2 and 4. It is possible to select the cuts {(1,3), (1,4)} and {(1,4),(2,4)} and both of these cut the cake into three pieces. It is not possible to select {(1,3),(2,4)}. The matrix M for this example is: -H 1234 1 0 0 1 1 20001 3 1 000 41 1 0 0 Give an algorithm for finding the solution that maximizes the number of pieces the cake can be cut in to