最长公共子序列的变种：带字符限制的最长公共子序列 题目描述： 给定两个字符串s和t，以及一个字符c，要求找到s和t的最长公共子序列，且这个子序列必须至少包含一个字符c。如果不存在这样的子序列，返回0。 解题过程： 问题分析： 我们需要找到两个字符串的最长公共子序列（LCS），但有一个额外限制：子序列必须包含特定字符c。这意味着我们需要在标准LCS的基础上增加对字符c出现情况的跟踪。 状态定义： 定义dp[ i][ j][ k ]表示考虑s的前i个字符和t的前j个字符时的状态，其中： k = 0：表示当前子序列中还没有包含字符c k = 1：表示当前子序列中已经包含了至少一个字符c 状态转移方程： 对于每个位置(i, j)： 如果s[ i-1] == t[ j-1 ]（字符匹配）： 如果匹配的字符等于c： dp[ i][ j][ 1] = max(dp[ i][ j][ 1], dp[ i-1][ j-1][ 0] + 1, dp[ i-1][ j-1][ 1 ] + 1) dp[ i][ j][ 1] = max(dp[ i][ j][ 1], dp[ i-1][ j-1][ 0 ] + 1) // 第一次包含c dp[ i][ j][ 1] = max(dp[ i][ j][ 1], dp[ i-1][ j-1][ 1 ] + 1) // 已经包含过c 如果匹配的字符不等于c： dp[ i][ j][ 0] = max(dp[ i][ j][ 0], dp[ i-1][ j-1][ 0 ] + 1) dp[ i][ j][ 1] = max(dp[ i][ j][ 1], dp[ i-1][ j-1][ 1 ] + 1) 如果字符不匹配： dp[ i][ j][ 0] = max(dp[ i][ j][ 0], dp[ i-1][ j][ 0], dp[ i][ j-1][ 0 ]) dp[ i][ j][ 1] = max(dp[ i][ j][ 1], dp[ i-1][ j][ 1], dp[ i][ j-1][ 1 ]) 初始化： dp[ 0][ j][ 0] = 0, dp[ 0][ j][ 1 ] = -∞（表示不可达） dp[ i][ 0][ 0] = 0, dp[ i][ 0][ 1 ] = -∞ dp[ 0][ 0][ 0] = 0, dp[ 0][ 0][ 1 ] = -∞ 最终结果： 结果是dp[ len(s)][ len(t)][ 1 ]，如果这个值小于0则返回0。 示例演示： 假设s = "abcde", t = "ace", c = 'c' 计算过程： 初始化所有dp值为0或-∞ 逐个字符比较，当遇到字符'c'时，更新包含c的状态 最终得到包含字符'c'的最长公共子序列长度为3（"ace"） 这个算法的时间复杂度是O(mn)，空间复杂度可以通过滚动数组优化到O(n)。