C. Constanze's Machine

help
,
1

Question

I was going through its solution, but I can’t get how they have formed a fibonacci relation. Can some one explain the logic?

2

@cubefreak777 can you explain me the logic why we are taking dpi = dpi-1 + dpi-2.

3

Suppose you have string abcuuuu , then suppose you have answer for dp_5 and dp_4 , (0-based indexing )
then for u at the the 6th index you have two options either to let it u , then the no. of ways will be dp_5 , or make uu as w ( u at index 5th and 6th) , then the no. of ways will be dp_4. so dp_6=dp_5+dp_4
Hence dp_i=dp_i-1 + dp_i-2

1 Like
4

Thanks @dhruv788