Количество различных слов размера N с не более чем K смежными гласными

Даны два целых числа N и K , задача состоит в том, чтобы найти количество различных строк, состоящих из строчных букв длины N , которые могут быть образованы не более чем K смежными гласными. Поскольку ответ может быть слишком большим, напечатайте answer%1000000007 .

Input: N = 1, K = 0
Output: 21
Explanation: All the 21 consonants are there which has 0 contiguous vowels and are of length 1.

Input: N = 1, K = 1
Output: 26

Подход: Идея решения этой проблемы основана на динамическом программировании. Выполните следующие шаги, чтобы решить проблему:

• Пусть dp[i][j] — количество способов составить различные строки длины i , где последние j символов строки — гласные.
• Итак, состояния динамического программирования:
  • Если j = 0 , то dp[i][j] = (dp[i-1][0] + dp[i-1][1] +……+ dp[i-1][K])*21 (представленный целочисленной переменной sum ) поскольку последний добавленный символ должен быть согласным, то только значение j станет равным 0 независимо от его значения в предыдущих состояниях.
  • Если i<j , то dp[i][j] = 0 . Так как невозможно создать строку, содержащую j гласных и имеющую длину меньше j .
  • Если i == j , то dp[i][j] = 5 ⁱ , потому что количество символов в строке равно количеству гласных, поэтому все символы должны быть гласными.
  • Если j<i , то dp[i][j] = dp[i-1][j-1]*5 , потому что строка длины i с последними j символами гласной может быть сделана только в том случае, если последний символ является гласной, а строка длины i-1 имеет последние j – 1 символ как гласные.
• В качестве ответа выведите сумму dp[n][0] + dp[n][1] + …… + dp[n][K] .

Ниже приведена реализация вышеуказанного подхода.

Временная сложность: O(N×K)
Вспомогательное пространство: O(N×K)