[Dynamic Programming] Practice Question

 

Q: Find the number of unique strings of which the length is L, given that the maximum number of consecutive vowels allowed is K. 

* There are 21 types of consonants and 5 types of vowels.

For example, L=4, K=1:

then allowed patterns are - 

CCCC

CCCV, CCVC, CVCC, VCCC, VCVC, VCCV, CVCV

 

This question can be easily handled with DFS. However, the approach would not be optimal as it involves unnecessary calculations.

Why is that?

Let's say we calculated all the cases for L=3. The results of L=3 can be used for L=4. And this is why we use dynamic programming for this question.

What information should we store?

dp[i][j]: the number of unique strings of which the length is i and exactly j last letters are vowels.

Then,

import math


def solution(m, n):
    if n == 0:
        return int(math.pow(21, m)) % (10**9+7)
    # dp[i][j]: # of words with length i with exactly last j letters are vowels
    dp = [[0] * (n+1) for _ in range(m+1)]
    dp[1][0] = 21
    dp[1][1] = 5
    for i in range(2, m+1):
        for j in range(n+1):
            if j > i: break
            if j == i:
                dp[i][j] = int(math.pow(5, i))
            elif j == 0:
                dp[i][j] = 21 * sum(dp[i-1][j] for j in range(n+1))
            else:
                dp[i][j] = 5 * dp[i-1][j-1]
    return sum(dp[-1][j] for j in range(n+1))


print(solution(2, 1))