algorithm - 用剪下的杂志字符生成一条消息（面试问题）

Question

这个问题来自Skiena的The Algorithm Deisgn Manual中的动态规划章节。

给出一个算法来确定您是否可以通过粘贴杂志上的剪裁来生成给定的字符串。您将获得一个函数，该函数将针对任何给定的字符位置识别字符及其在页面反面的位置。

我通过回溯解决了这个问题，但由于它在动态编程一章中，我认为肯定有重复出现，我无法弄清楚。谁能给我一个提示？

Answer 1

您可以通过最大二分匹配来解决它。

给定字符串的每个字符 L 形成左集。（注意，如果字符串有重复字符，则重复字符）。

杂志的每一对字符（R1，R2）形成正确的集合。

如果 L=R1 或 L=R2，则 L 连接到 (r1,r2)。

在结果图中找到最大匹配。如果所有左顶点都是匹配的一部分，那么您就有了答案。如果不是，那么这样的字符串是不可能的。

有关算法，请参阅最大二分匹配。

不确定这是否是最佳选择，很抱歉没有按照要求准确回答。

Answer 2

如果您有递归回溯解决方案，则可以应用memoization，这是进行动态编程的一种方法。