Using dynamic programming to solve this problem

Problem 2 (30 points). You are given k distinet bins arranged in an ordered sequence. Your task is to throw n balls (in order) into these k bins. However, every ball has an associated weight with it. The task is set up in a way such that: You may throw a consecutive sequence of balls into the same bin. Once you move on from bin i, you cannot come back to throw later balls into it. Define the load of a bin as the total weight of all balls in it. Design and analyze an efficient DP algorithm to determine the balls contributing to the load on every bin so as to minimize the marimum load over all bins. In your solution, make sure to explicitly state: 1. the optimal substructure and why it is optimal, 3. whether your algorithm is bottom-up or top-down DP 4. the description of your algorithm, and 5. the time and space complexity of your algorithm. For example, suppose B = 20, 9, 15, 10, 32 are the weights of the balls and k = 3, then your algorithm should return 20,9], l215, 10], and 32], where i represents the list of balls corresponding to the load on bin i. The minimum mar load is 32 for the given input B, and there are no other ways to throw the balls differently so that the minimum max load over all bins is any lower. In case of multiple optimal solutions, your algorithm may output any one of them Problem 2 (30 points). You are given k distinet bins arranged in an ordered sequence. Your task is to throw n balls (in order) into these k bins. However, every ball has an associated weight with it. The task is set up in a way such that: You may throw a consecutive sequence of balls into the same bin. Once you move on from bin i, you cannot come back to throw later balls into it. Define the load of a bin as the total weight of all balls in it. Design and analyze an efficient DP algorithm to determine the balls contributing to the load on every bin so as to minimize the marimum load over all bins. In your solution, make sure to explicitly state: 1. the optimal substructure and why it is optimal, 3. whether your algorithm is bottom-up or top-down DP 4. the description of your algorithm, and 5. the time and space complexity of your algorithm. For example, suppose B = 20, 9, 15, 10, 32 are the weights of the balls and k = 3, then your algorithm should return 20,9], l215, 10], and 32], where i represents the list of balls corresponding to the load on bin i. The minimum mar load is 32 for the given input B, and there are no other ways to throw the balls differently so that the minimum max load over all bins is any lower. In case of multiple optimal solutions, your algorithm may output any one of them