求长度为n且最多含k个连续元音的单词数量（DP解法问询）

Hey there! Great call picking dynamic programming for this problem—your state definition dp[i][j] (length i, ending with j consecutive vowels) is already spot-on, that’s half the battle won. Let’s walk through the recurrence relations step by step to fill in the gaps.

Key Observations #

First, let’s lock in the constants to keep things clear:

• 21 available consonants, 5 available vowels
• We can’t have more than k consecutive vowels, so j only ranges from 0 to k (any state where j > k is invalid and we can ignore it)

Recurrence Relations #

We’ll split into two distinct cases based on whether the current character added is a consonant or vowel:

1. Case 1: j = 0 (current character is a consonant)
   When you add a consonant to any valid word of length i-1, the trailing consecutive vowels reset to 0. So we sum up all valid words of length i-1 (regardless of their trailing vowel count) and multiply by the number of consonants:

   dp[i][0] = (dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][k]) * 21
   

   To optimize this, you can track a running total of dp[i-1][0..k] so you don’t have to recalculate the sum from scratch every time.

2. Case 2: 1 ≤ j ≤ k (current character is a vowel)
   To end with exactly j consecutive vowels, the previous word must have ended with exactly j-1 consecutive vowels—we just add one more vowel to the end. Multiply by the number of vowels:

   dp[i][j] = dp[i-1][j-1] * 5
   

   This works because adding a vowel to a word ending with j-1 vowels extends the streak to j, and we know j doesn’t exceed k (since we’re only considering valid states).

Base Cases #

For words of length 1 (i=1):

• dp[1][0] = 21 (all single-character consonant words)
• dp[1][1] = 5 (all single-character vowel words)
• dp[1][j] = 0 for j > 1 (you can’t have 2+ consecutive vowels in a 1-character word)

Final Answer #

The total number of valid words of length n is the sum of all valid states for length n:

total = dp[n][0] + dp[n][1] + ... + dp[n][k]

Quick Example (n=2, k=1) #

Let’s test this to confirm it makes sense:

• dp[2][0] = (21 + 5) * 21 = 26 * 21 = 546 (all words where the second character is a consonant)
• dp[2][1] = dp[1][0] * 5 = 21 * 5 = 105 (words where first is consonant, second is vowel—since k=1, two consecutive vowels are invalid)
• Total valid words = 546 + 105 = 651. Which checks out: total unrestricted words are 26²=676, minus invalid two-vowel words (5²=25) gives 651. Perfect!

内容的提问来源于stack exchange，提问作者akashking