最长公共子序列的变种：带字符出现次数限制的最长公共子序列

题目描述：
给定两个字符串s和t，以及一个字符c和整数k。要求找到s和t的最长公共子序列，且该子序列中字符c出现的次数不超过k次。请设计动态规划算法解决此问题。

解题过程：

1. 问题分析：

• 这是标准最长公共子序列(LCS)问题的变种
• 增加了额外限制：特定字符c在公共子序列中的出现次数不能超过k
• 需要在标准LCS状态基础上增加一维来记录字符c的出现次数

2. 状态定义：
   定义dp[i][j][x]表示：

• 考虑s的前i个字符和t的前j个字符
• 在它们的公共子序列中，字符c恰好出现了x次
• 这种情况下能得到的最长公共子序列长度

3. 状态转移方程：
   情况1：s[i] == t[j]

• 如果s[i] == c：
  • 如果x > 0：dp[i][j][x] = max(dp[i][j][x], dp[i-1][j-1][x-1] + 1)
  • 如果x == 0：不能选择这个字符，因为选择后c的出现次数会变成1
• 如果s[i] != c：
  • dp[i][j][x] = max(dp[i][j][x], dp[i-1][j-1][x] + 1)

情况2：s[i] != t[j]

• dp[i][j][x] = max(dp[i-1][j][x], dp[i][j-1][x])

4. 边界条件：

• dp[0][j][x] = 0（空字符串s）
• dp[i][0][x] = 0（空字符串t）
• 当x > 0时，dp[0][0][x] = -∞（不可能情况）
• dp[0][0][0] = 0（两个空字符串）

5. 算法步骤：

初始化dp为三维数组，大小为(len(s)+1) × (len(t)+1) × (k+1)
将所有元素初始化为0或负无穷（表示不可能状态）

for i from 0 to len(s):
    for j from 0 to len(t):
        for x from 0 to k:
            if i == 0 or j == 0:
                if x == 0: dp[i][j][x] = 0
                else: dp[i][j][x] = -∞
            else:
                # 不选择当前字符
                dp[i][j][x] = max(dp[i-1][j][x], dp[i][j-1][x])
                
                # 如果字符匹配，考虑选择当前字符
                if s[i-1] == t[j-1]:
                    if s[i-1] == c and x > 0:
                        dp[i][j][x] = max(dp[i][j][x], dp[i-1][j-1][x-1] + 1)
                    elif s[i-1] != c:
                        dp[i][j][x] = max(dp[i][j][x], dp[i-1][j-1][x] + 1)

# 最终答案是所有x ≤ k中的最大值
answer = max(dp[len(s)][len(t)][x] for x in range(0, k+1))

6. 复杂度分析：

• 时间复杂度：O(m × n × k)，其中m和n分别是字符串s和t的长度
• 空间复杂度：O(m × n × k)，可通过滚动数组优化到O(n × k)

7. 示例验证：
   设s = "abcbc", t = "acbcb", c = 'b', k = 1

• 标准LCS："acbc"（长度为4，包含2个'b'）
• 带限制的LCS："acc"（长度为3，包含0个'b'）或"acb"（长度为3，包含1个'b'）
• 算法应该返回3

这个解法通过增加状态维度来记录约束条件，是处理带限制的LCS问题的通用方法。