1 Overview

develop an algorithm to count the number of unique arrangements of pieces of candy. Designing and implementing this solution will require you to model the problem using dynamic programming, then understand and implement your model.

2 Problem Description

The Bitmans Confectionary Company (BCC) is a world-famous candy-making company, and their most popular product is the Bitmans Sampler, which has a variety of different chocolate candies arranged in a spiral pattern. BCC sells the samplers using the tagline No two alike! so its important to know how many different samplers they can put together. The samplers contain a number of different types of candies, which can be one of two sizes, square or long, which is a candy that is twice as long as a square but has the same width and height. BCC is always developing new types of candies and sells many different sizes of samplers, so we need to be able to answer this question for many different values. Your algorithm should be able to take in three parameters and compute the number of samplers possible. The three parameters are n, the size of the sampler (given in units of squares); s, the number of varieties of square candies that BCC makes; and `, the number of varieties of long candies. For example, BCC would be able to make 11 samplers of size 4 using one square (milk chocolate) and two long candies (caramel cookie crunch and toffee surprise)

include brief answers to 8 questions. Note that you must use dynamic programming to solve these problems.

1. How you can break down a large problem instance into one or more smaller instances? Your answer should include how the solution to the original problem is constructed from the subproblems and why this breakdown makes sense.

2. What recurrence can you use to model this problem using dynamic programming?

3. What are the base cases of this recurrence?

4. What data structure would you use to store the partial solutions to this problem? Justify your answer.

5. Describe a pseudocode algorithm that uses memoization to compute the number of samplers.

6. What is the time complexity of your memoized algorithm?

7. Describe an iterative algorithm for this problem.

8. Can the space complexity of the it

sample input text:

7

1. 1 100

4 1 2

3 2 2

6 2 1

5 5 2

10 5 2

20 6 4

sample outout:

1

11

16

169

4185

18727907

22913358946631680

Milk chocolate Caramel ? Toffee Note that we consider samplers with the same contents in a different order to be different. Also, this example is displayed in a line rather than a spiral for convenience. Milk chocolate Caramel ? Toffee Note that we consider samplers with the same contents in a different order to be different. Also, this example is displayed in a line rather than a spiral for convenience