### acash's blog

By acash, history, 4 weeks ago, , Given a word length n and max number of consecutive vowels k ,we need to tell how many words that we can form using given constraints.

n=3 and k=2 means we have to tell the number of words of length 3 and in which we can use at most k consecutive vowels.  Comments (5)
 » Define $dp_{i, j}$ equal to number of words of length $i$ such that no $k$ consecutive letters are vowel and $j$ last letters are vowel, you should be able to fill this on your own.
•  » » » I think DeadlyCritic gave you a good reply. How do you find $dp_{i,j}$? This is an answer for the words of length $i$, such that exactly last $j$ letters are vowels (and $j$ must not exceed $k$, otherwise $dp_{i,j} = 0$).Obviously, if $j > i$, $dp_{i,j} = 0$ (there can't be more letters in the word than its length).If $j = i$, it is just the number of words of length $i$, all consisting from vowels ($5^i$).For $j < i$, you try to understand, how many words of length $i$ with last $j$ letters being vowels exist, knowing the number of all words of length $i - 1$. If you append a consonant ($j = 0$) to the word of length $i-1$, then any of $dp_{i-1,j}$ words will work (so $dp_{i,0}$ is their sum). If you append a vowel ($j \ne 0$), then any of $dp_{i-1,j}$ words will work, apart from $j = k$ (because you add one vowel, so there cannot be already k vowels in the end of the $i-1$-word).