给定序列 S 和 T，找到一个序列 X 和 Y，使得 S 和 T 属于 X 和 Y 的洗牌。（X 和 Y 可能不存在）
Given sequence S and T, find a sequence X and Y such that S and T belong to the shuffle of X and Y. (X and Y may not exist)
我必须制定一个动态规划算法来解决这个问题：给定序列 S 和 T，找到一个序列 X 和 Y，使得 S 和 T 属于 X 和 Y 的混洗。
序列 S 和 T 的长度均为 n 。
我们想找到一个序列 X 和一个序列 Y，每个长度为 k 和 l，使得 S 和 T 属于 X 和 Y 的洗牌积。知道 (k+l = n)
如何使用动态规划解决这个问题。我很想知道使用过去结果的政策是什么。目前我还不知道。
有人可以用 S = GTACA 和 T = AGCAT 做一个例子吗
让我们假设我的 table 看起来像这样：
我们希望绿色单元格提供序列 X 和 Y 或什么都不提供（在 X 和 Y 不存在的情况下）
我注意到在许多动态规划问题中，构建当前问题的过去解决方案是从左侧（红色）或顶部（黄色）或对角线（蓝色）的单元格 selected当前单元格（绿色轮廓）。鉴于我的具体问题，我仍然很难知道如何 select。
更新
当我尝试按照下面的答案找到最长的公共子序列时，我得到了 AGCA（来自下面建议的维基百科文章。）
我的动态规划table是这样的：
如果我写错了，请告诉我哪里改正。
这似乎是 Longest common subsequence problem 的伪装：给定 S 和 T，你找到最长的公共子序列。那将是 X。如果它们在 S 和 T 中以相同的顺序出现，则遗漏的元素将是序列 Y，或者如果它们不以相同的顺序出现，则表示不存在这样的 X 和 Y。
在你的例子中最长的公共子序列是ACA。因此 X = ACA 和 S 和 T 中遗漏的元素是 GT，在两者中出现的顺序相同。因此 Y = GT.
编辑： 您的动态规划 table 不正确。例如，在第 3 行和第 4 列中，单元格应具有两个序列 A 和 G，而不是单个序列 AG。引用自维基百科：
If they are not equal, then the longer of the two sequences [...] is retained. (If they are the same length, but not identical, then both are retained.)
这是完整的 table（没有空序列）：
| G T A C A
-------------------------------------------
A | A A A
G | G G A,G A,G A,G
C | G G A,G AC,GC AC,GC
A | G G GA AC,GA,GC ACA,GCA
T | G GT GA,GT AC,GA,GC,GT ACA,GCA
这为我们提供了 X 的两个解决方案，但其中只有一个为我们提供了有效的 Y：
- 如果 X =
ACA 那么 Y = GT 基于 S 和 T -- 有效的解决方案。
- 如果 X =
GCA 那么 Y = TA 基于 S 但 AT 基于 T - 所以这不是解决方案。
我承认以上答案不是问题的完整解决方案。根据我在下面的评论中给出的推理，只能得出 X 或 Y 是 LCS 的子序列。后续是什么，还有待确定。
我必须制定一个动态规划算法来解决这个问题：给定序列 S 和 T，找到一个序列 X 和 Y，使得 S 和 T 属于 X 和 Y 的混洗。
序列 S 和 T 的长度均为 n 。 我们想找到一个序列 X 和一个序列 Y，每个长度为 k 和 l，使得 S 和 T 属于 X 和 Y 的洗牌积。知道 (k+l = n)
如何使用动态规划解决这个问题。我很想知道使用过去结果的政策是什么。目前我还不知道。
有人可以用 S = GTACA 和 T = AGCAT 做一个例子吗 让我们假设我的 table 看起来像这样：
我们希望绿色单元格提供序列 X 和 Y 或什么都不提供（在 X 和 Y 不存在的情况下）
我注意到在许多动态规划问题中，构建当前问题的过去解决方案是从左侧（红色）或顶部（黄色）或对角线（蓝色）的单元格 selected当前单元格（绿色轮廓）。鉴于我的具体问题，我仍然很难知道如何 select。
更新
当我尝试按照下面的答案找到最长的公共子序列时，我得到了 AGCA（来自下面建议的维基百科文章。）
我的动态规划table是这样的：
如果我写错了，请告诉我哪里改正。
这似乎是 Longest common subsequence problem 的伪装：给定 S 和 T，你找到最长的公共子序列。那将是 X。如果它们在 S 和 T 中以相同的顺序出现，则遗漏的元素将是序列 Y，或者如果它们不以相同的顺序出现，则表示不存在这样的 X 和 Y。
在你的例子中最长的公共子序列是ACA。因此 X = ACA 和 S 和 T 中遗漏的元素是 GT，在两者中出现的顺序相同。因此 Y = GT.
编辑： 您的动态规划 table 不正确。例如，在第 3 行和第 4 列中，单元格应具有两个序列 A 和 G，而不是单个序列 AG。引用自维基百科：
If they are not equal, then the longer of the two sequences [...] is retained. (If they are the same length, but not identical, then both are retained.)
这是完整的 table（没有空序列）：
| G T A C A
-------------------------------------------
A | A A A
G | G G A,G A,G A,G
C | G G A,G AC,GC AC,GC
A | G G GA AC,GA,GC ACA,GCA
T | G GT GA,GT AC,GA,GC,GT ACA,GCA
这为我们提供了 X 的两个解决方案，但其中只有一个为我们提供了有效的 Y：
- 如果 X =
ACA那么 Y =GT基于 S 和 T -- 有效的解决方案。 - 如果 X =
GCA那么 Y =TA基于 S 但AT基于 T - 所以这不是解决方案。
我承认以上答案不是问题的完整解决方案。根据我在下面的评论中给出的推理，只能得出 X 或 Y 是 LCS 的子序列。后续是什么，还有待确定。