带m个子串拆分限制的LCS（最长公共子序列）计数问题求解

这个问题可以通过三维动态规划求解，核心是把拆分次数、U的匹配进度、S的遍历进度都纳入状态定义：

状态定义 #

设 dp[i][j][k] 表示遍历到S的前i个字符时，已经匹配了U的前j个字符，且已经拆分成k个连续子串的合法方案总数。

转移逻辑 #

我们分两种情况处理每个S的字符：

• 不使用当前S的第i个字符：直接继承前i-1个字符的状态，即 dp[i][j][k] += dp[i-1][j][k]
• 使用当前S的第i个字符：仅当S[i-1] == U[j-1]（字符串下标从0开始）时合法，此时又分两种子场景：
  1. 当前字符属于第k个拆分段的后续字符：可以从dp[i-1][j-1][k]转移而来，相当于把当前字符追加到正在匹配的第k个分段末尾
  2. 当前字符是第k个拆分段的第一个字符：可以从dp[i-1][j-1][k-1]转移而来，相当于新开启一个拆分段

边界条件 #

• dp[0][0][0] = 1：空字符串S匹配空字符串U，拆分0段，仅1种合法方案
• 任意i，dp[i][0][0] = 1：匹配空U不需要任何分段，仅1种方案
• 其余初始状态均为0

前置剪枝 #

计算前可以先处理边界情况直接返回结果：

• 若m=0：仅当U也为空时返回1，否则返回0
• 若U的长度小于m：无法拆分出m个非空连续子串，直接返回0

空间优化实现 #

由于计算第i个字符的状态仅依赖第i-1个字符的状态，我们可以用滚动数组把三维空间压缩到二维，降低空间开销：

def lcs(S, U, m):
    n, t = len(S), len(U)
    # 前置剪枝
    if m == 0:
        return 1 if t == 0 else 0
    if t < m:
        return 0
    # 滚动数组初始化，prev_dp存储上一轮S前i-1个字符的状态
    prev_dp = [[0] * (m + 1) for _ in range(t + 1)]
    prev_dp[0][0] = 1
    for i in range(1, n + 1):
        # 先继承不使用当前S字符的状态
        curr_dp = [row[:] for row in prev_dp]
        for j in range(1, t + 1):
            if S[i-1] == U[j-1]:
                for k in range(1, m + 1):
                    curr_dp[j][k] += prev_dp[j-1][k] + prev_dp[j-1][k-1]
        prev_dp = curr_dp
    return prev_dp[t][m]

代入你给出的示例测试：lcs("aabacaab", "aab", 2) 输出结果为8，和预期一致。

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