how to get the recurrence relation?

f(n)=f(n-1)+floor(n/2)+1 yeah this has to be the correct relation as you said earlier.

I was stuck at n=4 and checking with these solutions. Thank You!

HOW RECURRENCE IS REDUCING TIME COMPLEXITY , BECAUSE WE ARE DOING CALCULATION N-1 TIMES ,

BUT IF WE DO DIRECTLY PERMUTATION THEN I THINK TIME SHOULD BE LESS BUT ITS GIVING TLE

Can anyone guide me how to strengthen my MATHS, to solve these kind of problems on my own ?

Like I could not even think about this solution that I saw in this editorial!

K K K H K

H K K K H

these are also solutions,

bcz only for first kiss we need to follow trend which is mentioned in question

For n = 4 total combination are 16 and rejected are

KHHH

KHHK

KKHK

KKHH

HKHH

HKKH

KKKH

SO total ans are 9 why your code giving answer 10

What I think is 2^n - Total number where K and H are alternate