This is a post describing my solution for 617B - Chocolate.

For this problem, the key is recognizing that we can think of breaking the candy bar up into parts as a sequential decision process. Once we know how many ways we can break the candy bar at each stage, we can just apply the rule of product and multiply the number of ways local breaks to the candy bar to produce the total number of ways to break up the candy bar.

The process proceeds as follows. We proceed from left to right. We march along the candy bar until we get between two nuts. Between each pair of nuts, if there are some zeros, we have the option of including the zeros with either the left nut of the right nut. The number of choices we have is the number of zeros, plus one. We continue this for each pair of nuts separated by either none or some zeros.

To help visualize this process, consider the following diagram on the input sequence 10101:

Here is some text afterward.