基于动态规划统计字符串拆分为X份且每份含至少一个元音的方案数

问题分析 #

我们需要统计将长度≤100的字符串拆分为X份的合法方案数，要求每份至少包含一个元音（a/e/i/o/u，可自行扩展大小写支持）。核心前提：若字符串中元音总数小于X，直接返回0；否则通过动态规划计算合法拆分方式。

动态规划设计 #

1. 状态定义 #

设dp[i][j]表示字符串前i个字符拆分成j份的合法方案数（字符索引从1开始，方便处理边界）。

2. 预处理 #

遍历字符串，生成count_vowel数组：count_vowel[i]代表前i个字符中的元音总数，用于快速判断拆分合法性。

3. 状态转移方程 #

• 若count_vowel[i] < j，说明前i个字符的元音不足以拆成j份，dp[i][j] = 0。
• 否则，累加所有合法分割点m的dp[m][j-1]：要求m < i，且m到i之间至少有一个元音（即count_vowel[i] - count_vowel[m] >= 1），公式为：

  dp[i][j] = sum(dp[m][j-1] for m in 0..i-1 if count_vowel[i] - count_vowel[m] >= 1)
  

4. 初始条件 #

• dp[0][0] = 1：空字符串拆成0份，仅1种合法方案。
• 对于j > 0，dp[0][j] = 0：空字符串无法拆成非0份。
• 对于i > 0，dp[i][0] = 0：非空字符串无法拆成0份。

示例验证（以bcaeiouxtz、X=3为例） #

字符串元音位置为第3(a)、4(e)、5(i)、6(o)、7(u)位（索引从1开始），count_vowel[10] = 5（总元音数）。计算dp[10][3]时，累加所有满足count_vowel[m] ≤4且dp[m][2]合法的值，最终结果为6，与示例一致。

代码实现（Python） #

def count_split_schemes(s, x):
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
    n = len(s)
    # 预处理前i个字符的元音数量
    count_vowel = [0]*(n+1)
    for i in range(1, n+1):
        count_vowel[i] = count_vowel[i-1] + (1 if s[i-1] in vowels else 0)
    
    # 初始化DP数组
    dp = [[0]*(x+1) for _ in range(n+1)]
    dp[0][0] = 1
    
    for i in range(1, n+1):
        for j in range(1, x+1):
            if count_vowel[i] < j:
                dp[i][j] = 0
                continue
            # 累加合法分割点的方案数
            total = 0
            for m in range(i):
                if count_vowel[i] - count_vowel[m] >= 1:
                    total += dp[m][j-1]
            dp[i][j] = total
    
    return dp[n][x]

# 测试示例
s = "bcaeiouxtz"
x = 3
print(count_split_schemes(s, x))  # 输出6

优化说明 #

上述代码时间复杂度为O(n²x)，对于n≤100、x≤100的场景完全够用。若要进一步优化，可预处理前缀和数组，将内层累加操作从O(n)降为O(1)，优化后时间复杂度为O(nx)。

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