我必须制定一种动态编程算法来解决此问题：给定序列S和T，找到序列X和Y，使得S和T属于X和Y的随机排列。

Question

序列S和T的长度分别为n。我们想要找到一个序列X和一个序列Y，每个序列的长度为k a l，使得S和T属于X和Y的混洗产物。知道（k + 1 = n）

我该如何使用动态编程来解决这个问题。我有兴趣知道使用过去结果的政策是什么。到目前为止，我还不知道。

有人可以用S = GTACA和T = AGCAT做例子吗？假设我的表如下所示：

我们希望绿色单元格提供序列X和Y或不提供任何序列（在X和Y不存在的情况下）

我已经注意到，在许多动态编程问题中，从当前单元格的左侧（红色）或顶部（黄色）或对角线（蓝色）（绿色的轮廓线）中选择用于构建当前单元格的过去解决方案。 。考虑到我的具体问题，我仍然很难知道如何选择。

Answer 1