最长公共子序列问题的最优子结构

最长公共子序列问题的最优子结构是指，如果我们已经知道了两个字符串的某个子序列的最长公共子序列，那么我们可以通过这个子序列来推导出原始字符串的最长公共子序列。具体来说，设两个字符串分别为s1和s2，它们的长度分别为m和n，令LCS(i,j)表示s1[0:i]和s2[0:j]的最长公共子序列的长度，则有以下递推式：

LCS(i,j) = 0, if i=0 or j=0
LCS(i,j) = LCS(i-1,j-1)+1, if s1[i-1]=s2[j-1]
LCS(i,j) = max(LCS(i-1,j), LCS(i,j-1)), if s1[i-1]!=s2[j-1]

其中第一行表示当i=0或j=0时，LCS(i,j)为0；第二行表示当s1[i-1]=s2[j-1]时，LCS(i,j)可以由LCS(i-1,j-1)推导得到；第三行表示当s1[i-1]!=s2[j-1]时，LCS(i,j)可以由LCS(i-1,j)和LCS(i,j-1)中的较大值推导得到。

相关问题

1 写出最长公共子序列问题 最优子结构性质 2 写出最长公共子序列问题 求解递归式 3 设 X=( c, b, d, b)， Y=( b, a, b, d, b, b) 写出c表格和b表格 写出最长公共子序列长度和最长公共子序列

好的，让我来回答您的问题。

1. 最长公共子序列问题（Longest Common Subsequence，LCS）：给定两个序列X和Y，找到同时在两个序列中出现的最长子序列的长度。

最优子结构性质：设LCS(X,Y)表示序列X和Y的最长公共子序列，考虑X和Y的任意一个最长公共子序列Z，可以将Z分为两部分：Z'为Z去掉最后一个元素后得到的子序列，z为Z的最后一个元素。如果z在X和Y的LCS中，则LCS(X,Y)必然等于LCS(X',Y') + 1，其中X'和Y'为X和Y去掉最后一个元素后得到的子序列。否则，LCS(X,Y)等于LCS(X',Y)和LCS(X,Y')中的较大值。

2. 最长公共子序列问题的递归式：

设LCS(X,Y)表示序列X和Y的最长公共子序列的长度，则有：

LCS(X,Y) = 0，如果X或Y为空序列

LCS(X,Y) = LCS(X',Y') + 1，如果X和Y的最后一个元素相同

LCS(X,Y) = max(LCS(X',Y), LCS(X,Y'))，如果X和Y的最后一个元素不相同

其中X'和Y'分别为X和Y去掉最后一个元素后得到的子序列。

3. 设X=(c,b,d,b)，Y=(b,a,b,d,b,b)，则c表格和b表格如下：

c表格：

| | b | a | b | d | b | b |
|---|---|---|---|---|---|---|
| c | 0 | 0 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 1 | 1 | 1 | 1 |
| d | 0 | 0 | 1 | 2 | 2 | 2 |
| b | 0 | 1 | 1 | 2 | 2 | 3 |

b表格：

| | b | a | b | d | b | b |
|---|---|---|---|---|---|---|
| c | | | | | | |
| b | | ↖ | ← | ↖ | ← | ↖ |
| d | | | ↖ | ← | ↖ | ← |
| b | | ↖ | ← | ↖ | ← | ↖ |

最长公共子序列的长度为3，一个可能的最长公共子序列为bdb。

最长公共子序列问题c

最长公共子序列问题是指给定两个序列，找到它们最长的公共子序列。下面是求解最长公共子序列问题的算法描述和步骤：

算法描述：
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：

1. 如果Xi和Yj的最后一个元素相同，则c[i][j]=c[i-1][j-1]+1；
2. 如果Xi和Yj的最后一个元素不同，则c[i][j]=max(c[i][j-1],c[i-1][j])。

步骤：
1. 初始化一个二维数组c，用于存储最长公共子序列的长度；
2. 将c的第一行和第一列全部初始化为0；
3. 从第二行和第二列开始，按照上述递归关系式计算c[i][j]的值；
4. 最终c[m][n]即为最长公共子序列的长度；5. 可以通过回溯c数组，找到最长公共子序列的具体内容。

下面是一个Python实现的例子：

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0] * (n + 1) for i in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i][j - 1], c[i - 1][j])
    return c[m][n]

X = "acbcf"
Y = "abcdaf"
print("最长公共子序列的长度为：", lcs(X, Y))