Approach?

I want to know how to approach this question in what direction to think so that i can solve it on my own.

Thank you.

Re: Approach?

Problem is tagged with dynamic programming

First, think about each possible configuration of the current state when you add next song

Second, think about techniques of DP - compression

Re: Approach?

well let x[n] be the number of sequences that finish with 1 and y[n] be the number of sequences that finish with 2 of the length n, x[0] = y[0] = 1, x[1] = y[1] = 1, the recurent formula for this is x[n] = y[n - 1] + y[n - 2] + y[n - 3] + .. + y[n - b] and y[n] = x[n - 1] + x[n - 2] + x[n - 3] + .. + x[n - a], basicly for a sequance of n + 1 you must think of the number of ways that the sequance will finish with 1 or with 2

*Edited by author 11.08.2017 04:09*

Re: Approach?

I am sorry but I still didn't understand, why x is dependent on y. Won't Y[] include cases having consecutive A times 1 and moreover won't Y[] Include duplicate cases ? I am sorry but I am new to this so that's why I am asking.

Re: Approach?

well let's approuch one case where your array is finishing with 1 but no more than "a" times in a row, because the 1 array is dependent from array of 2 and array 2 is alwais finishing with 2 it will look like this 12.... that is y[n] = x[n - 1], than 112... that is y[n] = x[n - 1] + x[n - 2], than 111...112.... which is y[n] = x[n] + x[n - 1] + x[n - 2] + ... + x[n - a] and is the same in the second case