最长重复子序列动态规划：奇数重复字符边缘问题求解

问题根源 #

原代码的核心错误在于：仅通过i≠j判断索引不重叠，但未限制同一字符的配对次数不能超过原字符串中该字符出现次数的一半（即每个字符最多只能被分配到两个子序列中各一次，总次数不超过floor(count(c)/2)）。以输入'AXXXA'为例，X出现3次，最多只能配对1次，但原代码允许将第三个X同时与前两个X配对，导致生成无效的XX结果（实际需要4个X才能支持长度为2的重复子序列）。

另外，直接检查字符是否已在DP子序列中的方案不可行——比如'AAJDDAJJTATA'中A出现4次，应该允许配对两次，而简单的存在检查会阻止第二次配对，破坏正确结果。

修正方案 #

我们需要在DP状态转移时，跟踪每个字符在当前子序列中的出现次数，确保不超过该字符允许的最大配对次数（即原字符串中字符出现次数//2）。具体步骤：

1. 先统计每个字符在原字符串中的出现次数，计算每个字符最多可被加入结果的次数（max_usage[c] = count(c)//2）。
2. 在尝试配对字符时，检查当前字符在DP子序列中的出现次数是否未达上限，再决定是否添加该字符。
3. 比较候选子序列与当前DP状态的长度，选择最长的子序列作为当前状态的结果。

修正后的代码 #

from collections import Counter

s = 'AXXXA'
char_count = Counter(s)
# 每个字符最多可在结果中出现的次数：原次数的一半（向下取整）
max_usage = {c: cnt // 2 for c, cnt in char_count.items()}

n = len(s)
# dp[i][j]表示s前i个字符和前j个字符中，满足要求的最长重复子序列
dp = [['' for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i != j and s[i-1] == s[j-1]:
            current_char = s[i-1]
            # 检查当前字符在dp[i-1][j-1]中的出现次数是否未达上限
            current_in_dp = dp[i-1][j-1].count(current_char)
            if current_in_dp < max_usage[current_char]:
                candidate = dp[i-1][j-1] + current_char
                # 选择最长的子序列作为当前状态
                dp[i][j] = max(candidate, dp[i-1][j], dp[i][j-1], key=len)
            else:
                # 已达上限，取之前的最长子序列
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)

print(dp[n][n])

测试验证 #

• 输入'AXXXA'时，代码会返回'X'或'A'（取决于max函数在长度相同时的选择），符合预期。
• 输入'AAJDDAJJTATA'时，A的max_usage为2，允许在结果中出现两次，不会影响正确的长重复子序列生成。

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