# usaco-1-1-prob4-dp

Here is a very beautiful solution using **dynamic programming** with $O(n)$ time complexity.

## Prob 4. Broken Necklace

I get a very elegant solution using **dynamic programming** idea. Just with a $O(n)$ time complexity.

Create a new variable type as

`NODE`

, storing the`left hand side`

and`right hand side`

beads with`red`

and`blue`

color.We cut the necklace into a linear string, then find another one to link it.

Why we do this?

Because we want to find the correct count of left/right hand side beads.

What will happen if there is just one necklace not two?

Then think about the bead count on the left or right side.

Left side end cannot count

`left hand side`

beads, although it should be a rounded necklace rather than a linear string.It is the same for the

`right hand side`

beads.

**From left to right**, count the`left hand side`

beads with**dp transform function**:1

2

3

4

5

6if beads[i - 1] == 'r'

neck[i].left_hand_side_blue_num = 0

and neck[i].left_hand_side_red_num = neck[i - 1].left_hand_side_red_num

if beads[i - 1] == 'b'

neck[i].left_hand_side_red_num = 0

and neck[i].left_hand_side_blue_num = neck[i - 1].left_hand_side_blue_num**From right to left**, count the`right hand side`

beads with**dp transform function**. (you can think about it, read the code, or see the**dp transform function**I wrote for**left to right**direction)Finally, let’s count!

Remember that there only need to read

`beads_num - 1`

times, since we only need to count one end for one direction, so we omitted the other end.So

`left hand side`

count need only considering the left side of the string, from`bead_num + 1`

to`2 * bead_num - 1`

.So

`right hand side`

count only consider the right side of string, from 0 to`beads_num - 1`

.

1 | /* |