How to use dynamic programming to solve this problem? I used fibonacci.

As far as I understand, this problem is about combinations and not about fibonacci.

If there was only the first condition, then for any N we have only 2 possibilities to create the flag.
That is, f(1) = 2, f(2) = 2, f(3) = 2, f(4) = 2, ..., f(N) = 2;
This is true, because the choice of the first stripe determines the rest of the flag automatically. If you choose the first stripe to be white-colored then you are destined to choose the red stripe to be the second one. And vice versa. Don't make my words a HOLY WISDOM - think about it till you can feel it yourself. Don't read next, until you fully and completely get it.

The second condition is here to complicate your life. It doesn't do anything to our function f(x) if x equals to 1 or 2. That is, f(1) and f(2) are still equal to 2.
(By the way, I've just noticed that I've pulled the function from under the pillow. Well, in my mind this function returns the amount of different flags that can be created if you need to make it from x stripes. Ok, now we're moving on...)

But it allows us to INSERT the blue stripe between the two: white and red stripes.

This concept of INSERTION is really the key here. Think about it. If you were supposed to gain anything intellectually from solving this task at all, I bet, it was this very concept.

If we have some sequence of 2-colored flag: WRWRWRWRWRWRWR (White and Red), and this sequence contains all the N stripes that we need, then we really don't have any place to INSERT our blue stipe.
You think, ok, that's fair, and remove one of the stipes (e.g. the left-most). Now you have the place for your blue stripe ... and you can insert it in many ways: wBrwrwrwrwr or wrBwrwrwrwr or wrwBrwrwrwr ... well, you get the point :)
This way, by removing one of the stripes you have created X COMBINATIONS. This word is also important, that is why it is all upper-case :)

If you remove ONE MORE stripe (think about removing as n - 1 or better n--), you now have to INSERT 2 blue stripes somewhere in the sequence wrwrwrwrwrwr...
E.g. wBrBwrwrwrwrwrwr, or wBrwrwrwrwrwrwBr. Now there should be more COMBINATIONS than in the previous case (figure out yourself, how many :) ).

The last point I want to make is that you have to know your limits. That is, you have to understand when to stop removing stipes from the flag and stop INSERTING blue stripes in it. When you get to this point (keeping in mind all the previous points), you will figure this out by yourself easily...

Edited by author 20.08.2015 02:16

Edited by author 20.08.2015 02:18

Edited by author 20.08.2015 02:23

Edited by author 20.08.2015 02:23

Edited by author 20.08.2015 02:25

Edited by author 20.08.2015 02:26

Edited by author 20.08.2015 02:27

Edited by author 20.08.2015 02:27

Edited by author 15.10.2016 20:15

Edited by author 15.10.2016 20:16

Edited by author 15.10.2016 20:20

Edited by author 15.10.2016 20:21

Edited by author 15.10.2016 20:21

This is really extremely helpful in reasoning about the problem, thank you

Егору зачет! За крутое решение и за знание англ)

lol