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.
I know its a dynamic programming problem but unable to figure out the recurrence.Please help!
word can contain letters only 21 consonants and 5 vowels
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 tried but not getting can you please help in finding the recurrence.I am new to DP
Here is an almost identical problem and the first answer is very understandable (but instead of solving the recurrence you would use DP) https://math.stackexchange.com/q/2023212/25959
And here is a general way for counting strings accepted by a DFA: https://web.cs.ucdavis.edu//classes/120/spring10/count.pdf
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).