For all the problems, I just need the idea for the dynamic programming. I dont need the coding part. Thank you so much.

1. (8 points) Over break, you take up bricklaying. For your first assignment, you have been asked to complete a brick wall where someone else has already built the first row of bricks. This wall is being built with bricks of length 1 , 2, and 3. As every builder knows, the bricks in a row need to "connect" the bricks below - that is, for any two neighboring bricks in the first row, there has to be a brick above that covers the connection between the bricks. For example, suppose the first wall's first row consists of bricks with lengths 2,3,1,3,2 as follows: Then it is possible to start the second row with a brick of length 1 (see below on the left), but it isn't possible to start the second row with a brick of length 2 since that makes the brick boundaries line up: Not happy with finding one way to build the next layer, you decide to count all the ways to build it. Specifically, you want to take n bricks with a sequence of lengths 1,2,,n, and calculate the number of ways the next layer of bricks can be built so that none of the brick boundaries line up. For example, with n=2, 1=1, and 2=2, there are two possibilities: Give an efficient dynamic programming solution to count number of ways to build the next level. You may find it helpful to think about the problem in terms of N, the total length of bricks in the first layer. (Note that n and N are asympototically equal.) 2. (8 points) Unfortunately for your wall-building plans, you discover that there are only k length-3 bricks. (You still have an unlimited supply of the other sizes.) With this extra constraint, you give up on counting the total number of solutions, but still want to see if you can build the next layer. Give a dynamic programming algorithm with running time O(Nk) that determines if the next layer can be built using at most k length-3 bricks so that none of the brick boundaries line up. 3. (8 points) Wall building turns out to be hard work so you get a new job, this time in a chocolate factory. The machine that makes chocolate bars creates sheets of chocolate sectioned into an nm grid of little squares. Your company has discovered that square pieces of chocolate sell better so your job is to split the sheet into square pieces (of any size). To save effort, you want to do this in as few "breaks" as possible, where a break goes all the way along one dimension of the piece, splitting an ab piece into either an a1b piece and an a2b piece (with a1+a2=a ) or an ab1 piece and an ab2 piece (with b1+b2=b ). Give an efficient dynamic programming algorithm to compute the smallest number of breaks needed. 1. (8 points) Over break, you take up bricklaying. For your first assignment, you have been asked to complete a brick wall where someone else has already built the first row of bricks. This wall is being built with bricks of length 1 , 2, and 3. As every builder knows, the bricks in a row need to "connect" the bricks below - that is, for any two neighboring bricks in the first row, there has to be a brick above that covers the connection between the bricks. For example, suppose the first wall's first row consists of bricks with lengths 2,3,1,3,2 as follows: Then it is possible to start the second row with a brick of length 1 (see below on the left), but it isn't possible to start the second row with a brick of length 2 since that makes the brick boundaries line up: Not happy with finding one way to build the next layer, you decide to count all the ways to build it. Specifically, you want to take n bricks with a sequence of lengths 1,2,,n, and calculate the number of ways the next layer of bricks can be built so that none of the brick boundaries line up. For example, with n=2, 1=1, and 2=2, there are two possibilities: Give an efficient dynamic programming solution to count number of ways to build the next level. You may find it helpful to think about the problem in terms of N, the total length of bricks in the first layer. (Note that n and N are asympototically equal.) 2. (8 points) Unfortunately for your wall-building plans, you discover that there are only k length-3 bricks. (You still have an unlimited supply of the other sizes.) With this extra constraint, you give up on counting the total number of solutions, but still want to see if you can build the next layer. Give a dynamic programming algorithm with running time O(Nk) that determines if the next layer can be built using at most k length-3 bricks so that none of the brick boundaries line up. 3. (8 points) Wall building turns out to be hard work so you get a new job, this time in a chocolate factory. The machine that makes chocolate bars creates sheets of chocolate sectioned into an nm grid of little squares. Your company has discovered that square pieces of chocolate sell better so your job is to split the sheet into square pieces (of any size). To save effort, you want to do this in as few "breaks" as possible, where a break goes all the way along one dimension of the piece, splitting an ab piece into either an a1b piece and an a2b piece (with a1+a2=a ) or an ab1 piece and an ab2 piece (with b1+b2=b ). Give an efficient dynamic programming algorithm to compute the smallest number of breaks needed