动态规划最长公共子序列递归结构

动态规划最长公共子序列的递归结构可以通过以下方式描述：

假设有两个序列a和b，分别有m和n个元素。我们定义一个函数LCS(a, b)来表示序列a和b的最长公共子序列的长度。

当m=0或n=0时，LCS(a, b)的值为0，因为其中一个序列为空，所以它们没有公共子序列。

当a[m-1]等于b[n-1]时，即a的最后一个元素等于b的最后一个元素，那么LCS(a, b)的值可以通过LCS(a[:m-1], b[:n-1])的值加1得到，因为最长公共子序列中包含了这两个相等的元素。

当a[m-1]不等于b[n-1]时，即a的最后一个元素不等于b的最后一个元素，那么LCS(a, b)的值可以通过LCS(a[:m-1], b)和LCS(a, b[:n-1])的值中的较大值得到，因为最长公共子序列要么包含a的最后一个元素，要么包含b的最后一个元素。

综上所述，可以得到递归结构如下：

LCS(a, b) = 0, if m = 0 or n = 0
LCS(a, b) = LCS(a[:m-1], b[:n-1]) + 1, if a[m-1] = b[n-1]
LCS(a, b) = max(LCS(a[:m-1], b), LCS(a, b[:n-1])), if a[m-1] != b[n-1]

这个递归结构可以作为动态规划最长公共子序列问题的基础，通过填充一个二维数组来实现动态规划的解法。每个数组元素dp[i][j]表示序列a[:i]和b[:j]的最长公共子序列的长度。通过填充这个数组，可以得到最终的最长公共子序列的长度。

相关问题

最长公共子序列问题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))

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。